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

更新於：2020年12月2日

202 次瀏覽

開啟您的職業生涯

完成課程獲得認證

開始學習
廣告