Python程式：查詢將一個字串變成另一個字串的子字串所需的最小操作次數

假設我們有兩個字串 s 和 t，我們需要找到使 t 成為 s 的子字串所需的最小操作次數。在每次操作中，我們可以在 s 中選擇任何位置並將該位置的字元更改為任何其他字元。

例如，如果輸入為 s = "abbpqr"，t = "bbxy"，則輸出為 2，因為我們可以取子字串 "bbpq" 並將 'p' 更改為 'x'，將 'q' 更改為 'y'。

為了解決這個問題，我們將遵循以下步驟：

• k := t 的大小，n := s 的大小
• ans := 10^10
• 對於 i 從 0 到 n - k，執行以下操作：
  • ss := s 的子字串（從索引 i 到 i+k-1）
  • ans := ans 和 s 和 t 之間不匹配字元數量的最小值
• 返回 ans

讓我們看看下面的實現來更好地理解：

示例

 線上演示

class Solution:
   def solve(self, s, t):
      k, n = len(t), len(s)
      ans = 10**10
      for i in range(n - k + 1):
         ss = s[i:i+k]
         ans = min(ans, sum(ss[j]!=t[j] for j in range(k)))
      return ans
ob = Solution()
print(ob.solve("abbpqr", "bbxy"))

輸入

"abbpqr", "bbxy"

輸出

2

Arnab Chakraborty

更新於: 2020年10月5日

620 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習