用 Python 编写程序，查找使一个字符串成为另一个字符串子字符串所需的最少操作数

pythonserver side programmingprogramming更新于 2026/1/7 4:28:17

假设我们有两个字符串 s 和 t，我们必须找到使 t 成为 s 子字符串所需的最少操作数。现在，在每个操作中，我们可以选择 s 中的任意位置并将该位置的字符更改为任何其他字符。

因此，如果输入为 s = "abbpqr", t = "bbxy"，则输出将为 2，因为我们可以取子字符串 "bbpq" 并将 'p' 更改为 'x' 和 'q'到"y"。

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

k := t 的大小，n := s 的大小
ans := 10^10
对于 0 到 n - k 范围内的 i，执行
- 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"))