วิธีตรวจสอบว่า Edit Distance ระหว่างสองสตริงเท่ากับ 1 ใน Python

ปัญหา

Edit Distance = 1 หมายถึง ต้องใช้การแก้ไขเพียง 1 ครั้ง: แทรก (Insert), ลบ (Delete), หรือแทนที่ (Replace) ตัวอักษร 1 ตัว

ตัวอย่าง: "hello" และ "heillo" → แทรก 'i' → True

แนวทางแก้ปัญหา

1. หากความยาวต่างกัน > 1 → False
2. ใช้ Two Pointers (i, j) เดินพร้อมกัน นับจำนวนความต่าง
3. จัดการกรณีความยาวต่างกัน (ขยับ pointer ไหนข้างยาว)

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

def solve(s, t):
    if abs(len(s) - len(t)) > 1:
        return False
    edit_dist_cnt = 0
    i = j = 0
    while i < len(s) and j < len(t):
        if s[i] != t[j]:
            if edit_dist_cnt == 1:
                return False
            if len(s) > len(t):
                i += 1
            elif len(s) < len(t):
                j += 1
            else:
                i += 1
                j += 1
            edit_dist_cnt += 1
        else:
            i += 1
            j += 1
    if i < len(s) or j < len(t):
        edit_dist_cnt += 1
    return edit_dist_cnt == 1

s = "hello"
t = "heillo"
print(solve(s, t))  # True

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

Input: "hello", "heillo"
Output: True