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 时，执行以下操作：
  • source_idx := 0
  • temp_index := target_idx
  • 当 source_idx < s_size 且 target_idx < t_size 时，执行以下操作：
    • 如果 s[source_idx] 等于 t[target_idx]，则：
      • target_idx := target_idx + 1
    • source_idx := source_idx + 1
  • 如果 temp_index 等于 target_idx，则：
    • 返回 -1
  • 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

Arnab Chakraborty

更新于：2020年12月2日

202 次浏览

开启您的职业生涯

完成课程获得认证

开始学习