Chương trình kiểm tra hai chuỗi có khoảng cách chỉnh sửa 0 hoặc 1 không bằng Python

Cho hai chuỗi S và T, kiểm tra xem chúng có khoảng cách chỉnh sửa 0 hoặc 1 hay không. Phép chỉnh sửa: xóa, thêm, hoặc thay thế một ký tự.

Ví dụ: S = "hello", T = "hallo" → True (khoảng cách 1).

Quy trình giải quyết

1. Nếu chênh lệch độ dài > 1, trả về False.
2. Duyệt hai chuỗi với hai con trỏ i, j và biến đếm count.
3. Khi ký tự khác nhau:
   • Nếu count == 1, trả về False.
   • Tùy theo độ dài chuỗi, tăng i hoặc j hoặc cả hai.
   • Tăng count.
4. Trả về True.

Ví dụ mã nguồn

class Solution:
    def solve(self, S, T):
        m, n = len(S), len(T)
        i, j = 0, 0
        count = 0
        if abs(m - n) > 1:
            return False
        while i < m and j < n:
            if S[i] != T[j]:
                if count == 1:
                    return False
                if m < n:
                    j += 1
                elif m > n:
                    i += 1
                else:
                    i += 1
                    j += 1
                count += 1
            else:
                i += 1
                j += 1
        return True

ob = Solution()
S = "hello"
T = "hallo"
print(ob.solve(S, T))  # Output: True

Đầu vào

"hello", "hallo"

Đầu ra

True