โปรแกรมหาจำนวนตัวอักษรที่ต้องเปลี่ยนเพื่อแก้คำผิดใน Python

กำหนดลิสต์ cities (ลำดับเมืองที่รถทัวร์ไป) และ roads (ถนนเดียทาง รูปแบบ [source, destination]) บางชื่อเมืองใน cities อาจสะกดผิด ต้องแก้โดยเปลี่ยนตัวอักษรน้อยที่สุด คืนค่าจำนวนตัวอักษรที่เปลี่ยน

ตัวอย่าง

อินพุต: cities = ["HWH", "DLI", "BGL"], roads = [["HWH", "DLI"], ["DLI", "BCT"], ["BCT", "HWH"]] → เอาต์พุต: 2

• เมือง "BGL" สะกดผิด ควรเป็น "BCT"
• ต้องเปลี่ยน 2 ตัวอักษร (G→C, L→T)

วิธีแก้ปัญหา

1. ฟังก์ชัน diff(a, b) นับตัวอักษรที่ต่างกันในตำแหน่งเดียวกัน
2. Dynamic Programming: arr[city] = ต้นทุนน้อยที่สุดถึงเมืองนี้ที่ขั้นตอนปัจจุบัน
3. เริ่มจากขั้นตอนที่ 0: ต้นทุนจาก cities[0] ไปทุกจุดเริ่มต้นของถนน
4. วนลูปขั้นตอนถัดไป: อัปเดต nxt[dest] จาก arr[src] + diff(cities[i], dest)
5. คืนค่า min(arr.values())

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

def diff(a, b):
    return sum(x != y for x, y in zip(a, b))

def solve(cities, roads):
    size = len(cities)
    arr = dict()
    junctions = set(r[0] for r in roads)
    
    for j in junctions:
        arr[j] = diff(cities[0], j)
    
    for i in range(1, size):
        nxt = dict()
        for r1, r2 in roads:
            if r1 in arr:
                cost = arr[r1] + diff(cities[i], r2)
                if r2 not in nxt or cost < nxt[r2]:
                    nxt[r2] = cost
        arr = nxt
    
    return min(arr.values())

print(solve(["HWH", "DLI", "BGL"], [["HWH", "DLI"], ["DLI", "BCT"], ["BCT", "HWH"]]))

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

Input:  ["HWH", "DLI", "BGL"], [["HWH", "DLI"], ["DLI", "BCT"], ["BCT", "HWH"]]
Output: 2

หลักการ: ใช้ Dynamic Programming บนกราฟถนน ระยะทาง = จำนวนตัวอักษรที่ต่างกัน (Hamming distance) หาเส้นทางที่มีต้นทุนรวมน้อยที่สุด