Chương trình tìm số ký tự cần sửa để sửa tên thành phố sai chính tả trong Python

Cho danh sách cities (thứ tự thăm) và roads (các đường một chiều (source, destination)). Một số tên trong cities bị sai chính tả. Sửa bằng cách thay đổi ít ký tự nhất sao cho chuỗi cities trở thành đường đi hợp lệ trong đồ thị roads. Trả về số ký tự thay đổi tối thiểu.

Ví dụ

Input: cities=["HWH","DLI","BGL"], roads=[["HWH","DLI"],["DLI","BCT"],["BCT","HWH"]] → Output: 2

"BGL" sai, sửa thành "BCT" (thay G→C, L→T = 2 ký tự). Đường đi: HWH→DLI→BCT hợp lệ.

Thuật toán (Dynamic Programming trên đồ thị)

Tìm đường đi độ dài len(cities) trong đồ thị roads, tối thiểu hóa tổng khoảng cách ký tự (Hamming distance) giữa cities[i] và tên thành phố thực tại bước i.

1. Hàm diff(a,b): đếm số vị trí ký tự khác nhau (giả định cùng độ dài)
2. DP trạng thái: arr[city] = chi phí nhỏ nhất đến city tại bước hiện tại
3. Khởi tạo: arr[j] = diff(cities[0], j) cho mọi city j là nguồn (xuất phát)
4. Lặp qua i=1..n-1:
   • Tạo nxt mới
   • Với mỗi đường (r1,r2): nếu r1 có trong arr, cập nhật nxt[r2] = min(nxt[r2], arr[r1] + diff(cities[i], r2))
5. Kết quả: min giá trị trong arr cuối cùng

Mã nguồn

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

def solve(cities, roads):
    size = len(cities)
    arr = {}
    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 = {}
        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"]]))  # Output: 2

Phân tích

• Độ phức tạp: O(L × |roads|) với L = len(cities)
• Giả định: tên thành phố cùng độ dài (zip dừng ở chuỗi ngắn hơn)
• Mở rộng: nếu độ dài khác nhau, dùng Levenshtein distance