Python - Kiểm tra hai chuỗi có đồng cấu (isomorphic) hay không

Hai chuỗi được gọi là đồng cấu (isomorphic) nếu các ký tự trong chuỗi thứ nhất có thể được thay thế để得到 chuỗi thứ hai, với ánh xạ một-một. Ta định nghĩa phương thức check_isomorphic nhận hai chuỗi, sử dụng mảng đánh dấu và ánh xạ dựa trên mã ASCII (ord).

Ví dụ

Minh họa:

MAX_CHARS = 256
def check_isomorphic(str_1, str_2):
    len_1 = len(str_1)
    len_2 = len(str_2)
    if len_1 != len_2:
        return False
    marked = [False] * MAX_CHARS
    map = [-1] * MAX_CHARS
    for i in range(len_2):
        if map[ord(str_1[i])] == -1:
            if marked[ord(str_2[i])]:
                return False
            marked[ord(str_2[i])] = True
            map[ord(str_1[i])] = str_2[i]
        elif map[ord(str_1[i])] != str_2[i]:
            return False
    return True

str_1 = 'aababa'
str_2 = 'xxyyxx'
print("Chuỗi thứ nhất:", str_1)
print("Chuỗi thứ hai:", str_2)
print("Chuỗi 'aab' và 'xxy' đồng cấu?", check_isomorphic("aab", "xxy"))
print("Chuỗi 'aab' và 'xyz' đồng cấu?", check_isomorphic("aab", "xyz"))

Kết quả

Chuỗi thứ nhất: aababa
Chuỗi thứ hai: xxyyxx
Chuỗi 'aab' và 'xxy' đồng cấu? True
Chuỗi 'aab' và 'xyz' đồng cấu? False

Giải thích

• Định nghĩa phương thức check_isomorphic nhận hai chuỗi.
• Nếu độ dài khác nhau, trả về False.
• Tạo mảng marked (đánh dấu ký tự chuỗi 2 đã dùng) và map (ánh xạ từ ký tự chuỗi 1 sang chuỗi 2).
• Duyệt qua từng ký tự: nếu chưa có ánh xạ, kiểm tra ký tự chuỗi 2 đã dùng chưa; nếu đã dùng thì False, ngược lại tạo ánh xạ.
• Nếu đã có ánh xạ nhưng không khớp, trả về False.
• Trả về True nếu duyệt hết không vi phạm quy tắc.