Khoảng cách chỉnh sửa (Levenshtein distance) = 1 nghĩa là chỉ cần một thao tác: chèn, xóa, hoặc thay thế một ký tự.
Ví dụ: "hello" vs "heillo" → chèn 'i' → True.
Thuật toán O(n)
- Nếu chênh lệch độ dài > 1 →
False. - Duyệt song song hai chuỗi, đếm số lần không khớp.
- Khi không khớp: nếu chuỗi dài hơn → bỏ qua ký tự ở chuỗi dài (giả lập xóa), nếu bằng nhau → bỏ qua cả hai (giả lập thay thế).
- Cuối cùng, nếu còn ký tự dư ở chuỗi nào → cộng 1 vào edit distance.
- Trả về
edit_dist == 1.
Triển khai
def solve(s, t):
if abs(len(s) - len(t)) > 1:
return False
edit_dist = 0
i = j = 0
while i < len(s) and j < len(t):
if s[i] != t[j]:
if edit_dist == 1:
return False
if len(s) > len(t):
i += 1
elif len(s) < len(t):
j += 1
else:
i += 1
j += 1
edit_dist += 1
else:
i += 1
j += 1
if i < len(s) or j < len(t):
edit_dist += 1
return edit_dist == 1
s = "hello"
t = "heillo"
print(solve(s, t)) # True
Đầu vào / Đầu ra
Input: "hello", "heillo"
Output: True