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

更新于: 2020年10月5日

620 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告