Giả sử chúng ta có một chuỗi chữ thường s. Bây giờ hãy xem xét một hoạt động, nơi chúng ta có thể xóa, chèn hoặc cập nhật bất kỳ ký tự nào trong s. Chúng ta phải đếm số lượng phép toán tối thiểu cần thiết để tạo s =(t nối t) cho bất kỳ chuỗi t nào.
Vì vậy, nếu đầu vào là s ="pqrxqsr", thì đầu ra sẽ là 2, bởi vì, chúng ta có thể cập nhật "x" bằng "p" và xóa "s", sau đó s là "pqrpqr", đây là s =t nối t, cho t ="pqr".
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- Xác định một hàm edit_distance (). Điều này sẽ mất s1, s2
- m:=kích thước của s1
- n:=kích thước của s2
- cur:=một danh sách mới từ phạm vi 0 đến n
- đối với tôi trong phạm vi từ 0 đến m - 1, thực hiện
- trước:=cur
- cur:=một danh sách với (i + 1) và n số 0
- đối với j trong phạm vi từ 0 đến n - 1, thực hiện
- cur [j + 1]:=prev [j] nếu s1 [i] và s2 [j] giống nhau về mặt khác (tối thiểu của cur [j], pres [j], pres [j + 1]) + 1
- return cur [n]
- Từ phương pháp chính, hãy thực hiện như sau -
- res:=kích thước của s
- đối với tôi trong phạm vi từ 0 đến kích thước là s-1, hãy thực hiện
- res:=tối thiểu của edit_distance (chuỗi con của s từ chỉ mục 0 đến i - 1, chuỗi con của s từ chỉ mục i đến cuối) và res
- trả lại res
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
def solve(s): def edit_distance(s1, s2): m, n = len(s1), len(s2) cur = list(range(n + 1)) for i in range(m): prev, cur = cur, [i + 1] + [0] * n for j in range(n): cur[j + 1] = (prev[j] if s1[i] == s2[j] else min(cur[j], prev[j], prev[j + 1]) + 1) return cur[n] res = len(s) for i in range(len(s)): res = min(edit_distance(s[:i], s[i:]), res) return res s = "pqrxqsr" print(solve(s))
Đầu vào
"pqrxqsr"
Đầu ra
None