Giả sử chúng ta có hai chuỗi s và t, chúng ta phải tìm số lượng phép toán tối thiểu cần thiết cho s để biến t trở thành chuỗi con của s. Bây giờ, trong mỗi thao tác, chúng ta có thể chọn bất kỳ vị trí nào trong s và thay đổi ký tự ở vị trí đó thành bất kỳ ký tự nào khác.
Vì vậy, nếu đầu vào là s ="abbpqr", t ="bbxy", thì đầu ra sẽ là 2, vì chúng ta có thể lấy chuỗi con "bbpq" và thay đổi 'p' thành 'x' và 'q' thành ' y '.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- k:=kích thước của t, n:=kích thước của s
- ans:=10 ^ 10
- đối với tôi trong phạm vi từ 0 đến n - k, thực hiện
- ss:=chuỗi con của s [từ chỉ mục i đến i + k-1]
- ans:=tối thiểu ans và số ký tự không trùng khớp của s và t
- trả lại ans
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
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