Chương trình kiểm tra một lần hoán vị có làm hai chuỗi bằng nhau không bằng Python

Cho hai chuỗi s, t cùng độ dài. Có thể hoán vị hai ký tự (có thể cùng vị trí) trong đúng một chuỗi. Kiểm tra có thể làm s == t không.

Ví dụ: s = "hello", t = "hlelo" → True (hoán vị 'e' và 'l').

Thuật toán giải quyết

• max_diffs = 2 (tối đa 2 vị trí khác nhau).
• Đếm diffs = số vị trí i mà s[i] != t[i].
• Tập hợp st (ký tự s tại vị trí khác), st2 (ký tự t tại vị trí khác).
• Nếu diffs > 2: False.
• Trả về True nếu (diffs == 0 hoặc diffs == 2) và st == st2 (cùng tập ký tự).

Ví dụ triển khai

def solve(s, t):
    max_diffs = 2
    diffs = 0
    st = set()
    st2 = set()
    for i in range(len(s)):
        if s[i] != t[i]:
            diffs += 1
        if s[i] not in st:
            st.add(s[i])
        if t[i] not in st2:
            st2.add(t[i])
        if diffs > max_diffs:
            return False
    return (diffs == 0 or diffs == 2) and len(st) == len(st2) and st == st2

s = "hello"
t = "hlelo"
print(solve(s, t))

Đầu vào

"hello", "hlelo"

Đầu ra

True