程序查找与python中的目标串联的最小子序列数

假设我们有两个字符串source和target，我们必须找到可以形成的source子序列的最小数量，这样，如果我们将它们串联起来，它将与target相同。如果没有这样的结果，则返回-1。

因此，如果输入类似于source =“ xyz” target =“ xyzyzz”，则输出将为3，因为我们可以将这些[“ xyz” +“ yz” +“ z”]连接起来

为了解决这个问题，我们将遵循以下步骤-

• s_size：= s的大小，t_size：= t的大小

• concat_count：= 0，target_idx：= 0

• 当target_idx <t_size时

• 返回-1

• 如果s [source_idx]与t [target_idx]相同，则

• source_idx：= source_idx +1

• target_idx：= target_idx + 1

• source_idx：= 0

• temp_index：= target_idx

• 而当source_idx <s_size和target_idx <t_size时，

• 如果temp_index与target_idx相同，则

• concat_count：= concat_count + 1

• 返回concat_count

让我们看下面的实现以更好地理解-

例 

class Solution:
   def solve(self, s, t):
      s_size, t_size = len(s), len(t)
      concat_count = 0
      target_idx = 0
      while target_idx < t_size:
         source_idx = 0
         temp_index = target_idx

         while source_idx < s_size and target_idx < t_size:
            if s[source_idx] == t[target_idx]:
               target_idx += 1
            source_idx += 1

         if temp_index == target_idx:
            return -1
         concat_count += 1
      return concat_count
ob = Solution()source = "xyz"
target = "xyzyzz"
print(ob.solve(source, target))

输入值

"xyz", "xyzyzz"

输出结果

3