Chương trình xác định hai chuỗi có gần nhau (close) trong Python

Hai chuỗi s, t gọi là close nếu biến đổi được nhau bằng 2 phép toán: (1) hoán đổi 2 ký tự bất kỳ; (2) đổi toàn bộ ký tự x thành y và ngược lại (swap toàn cục). Kiểm tra s và t có close không.

Ví dụ: s="zxyyyx", t="xyyzzz" → True. Biến đổi: "zxyyyx" → "zxxyyy" → "yxxzzz" → "xyyzzz".

Giải thuật

1. Nếu tập ký tự của s và t khác nhau → False.
2. Đếm tần suất ký tự của s và t.
3. Sắp xếp 2 mảng tần suất.
4. Nếu 2 mảng tần suất giống nhau → True, ngược lại False.

Lý do: phép (1) cho phép sắp xếp lại vị trí, phép (2) cho phép hoán đổi nhãn ký tự. Do đó chỉ cần cùng tập ký tự và cùng multiset tần suất.

Ví dụ minh họa

from collections import Counter

def solve(s, t):
    if set(s) != set(t):
        return False
    a = sorted(Counter(s).values())
    b = sorted(Counter(t).values())
    return a == b

s = "zxyyyx"
t = "xyyzzz"
print(solve(s, t))

Đầu vào

"zxyyyx", "xyyzzz"

Đầu ra

True