Chương trình tìm số phép toán tối thiểu để chuỗi này thành chuỗi con của chuỗi kia trong Python

Cho hai chuỗi s và t, tìm số phép toán tối thiểu để t trở thành chuỗi con của s. Mỗi phép toán chọn một vị trí trong s và thay ký tự đó thành ký tự bất kỳ.

Ví dụ, s = "abbpqr", t = "bbxy", đầu ra 2 (thay 'p'->'x', 'q'->'y' trong chuỗi con "bbpq").

Các bước giải quyết:

• k := len(t), n := len(s).
• ans := 10^10.
• Với i từ 0 đến n - k:
  • ss := s[i:i+k].
  • ans = min(ans, số ký tự khác nhau giữa ss và t).
• Trả về ans.

Ví dụ minh họa

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"))

Đầu vào

"abbpqr", "bbxy"

Đầu ra

2