Chương trình kiểm tra chuỗi đối xứng với cặp ký tự tương đương Python

Cho chuỗi s và danh sách cặp pairs ([a,b] nghĩa là a và b tương đương). Tương đương là bắc cầu: nếu a~b và b~c thì a~c. Kiểm tra s có phải palindrome dưới quan hệ tương đương không.

Ví dụ: s="raceckt", pairs=[["r","t"],["a","k"],["z","x"]] → True (vì a=k, r=t → "racecar").

Giải thuật (DFS tìm thành phần liên thông)

1. Xây đồ thị từ pairs
2. DFS từ mỗi nút tìm tất cả ký tự tương đương (thành phần liên thông)
3. Kiểm tra từng cặp ký tự đối xứng trong s: phải giống nhau hoặc thuộc cùng thành phần liên thông

Ví dụ triển khai

from collections import defaultdict

def solve(s, pairs):
    g = defaultdict(list)
    G = defaultdict(set)
    for x, y in pairs:
        g[x].append(x)
        g[y].append(y)
        g[x].append(y)
        g[y].append(x)
    
    def dfs(a, so_far):
        so_far.add(a)
        for elem in g[a]:
            if elem not in so_far:
                dfs(elem, so_far)
    
    for key in g:
        dfs(key, G[key])
    
    for i in range(len(s) // 2):
        if s[i] == s[-1-i] or (s[i] in G[s[-1-i]] or s[-1-i] in G[s[i]]):
            continue
        else:
            return False
    return True

print(solve("raceckt", [["r","t"],["a","k"],["z","x"]]))

Đầu vào

"raceckt", [["r","t"],["a","k"],["z","x"]]

Đầu ra

True