โปรแกรมตรวจสอบสองสตริงห่างกัน 0 หรือ 1 edit distance ใน Python

สมมติว่าเรามีสตริง S และ T ตรวจสอบว่าระยะห่างการแก้ไข (edit distance) เป็น 0 หรือ 1 หรือไม่ การแก้ไขคือ ลบตัวอักษร เพิ่มตัวอักษร หรือแทนที่ตัวอักษร

ตัวอย่าง: S = "hello", T = "hallo" ผลลัพธ์ True (edit distance = 1)

ขั้นตอนการแก้ปัญหา

1. m = len(S), n = len(T), i = j = 0, count = 0
2. ถ้า |m - n| > 1 คืนค่า False
3. วนลูป while i < m และ j < n:
   • ถ้า S[i] != T[j]:
     • ถ้า count == 1 คืนค่า False
     • ถ้า m < n: j += 1 (insert)
     • ถ้า m > n: i += 1 (delete)
     • อื่นๆ: i += 1, j += 1 (replace)
     • count += 1
   • อื่นๆ: i += 1, j += 1
4. คืนค่า True

ตัวอย่างโค้ด Python

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

อินพุต / เอาต์พุต

Input: "hello", "hallo"

Output: True