Isomorphic Strings

Q: Tại sao bạn cần hai bảng băm cho các chuỗi đẳng cấu?

Ánh xạ từ s sang t phát hiện một ký tự trong s được đổi tên thành hai ký tự khác nhau. Nó không phát hiện được hai ký tự trong s được đổi tên thành cùng một ký tự, như trong ab và aa . Ánh xạ từ t ngược lại s phát hiện trường hợp đó.

DễBăm

+10

Hai chuỗi đẳng cấu khi bạn có thể đổi tên các ký tự trong chuỗi thứ nhất để tạo thành chuỗi thứ hai. Mọi lần xuất hiện của một ký tự đều nhận cùng một tên mới, hai ký tự khác nhau không bao giờ nhận cùng một tên, và một ký tự có thể giữ nguyên tên. Với hai chuỗi s và t có cùng độ dài, hãy trả về true nếu chúng đẳng cấu và false nếu không.

Hàm

isIsomorphic(s: string, t: string) → boolean

sstring: chuỗi cần đổi tên, chữ cái và chữ số
tstring: chuỗi cần đạt tới, có độ dài bằng s
Trả vềboolean: đúng nếu việc đổi tên từng ký tự của s theo cách một-một tạo ra t

Ràng buộc

1 ≤ s.length ≤ 2 × 10⁴
t.length == s.length
s và t chỉ chứa chữ cái tiếng Anh và chữ số. Chữ hoa và chữ thường là các ký tự khác nhau.

Ví dụ

Đầu vào: s = "noon"t = "deed"
Đầu ra: true
Giải thích: Đổi tên n thành d và o thành e. Mọi vị trí đều phù hợp với cách đổi tên đó, và hai chữ cái có tên khác nhau.

Đầu vào: s = "moon"t = "deed"
Đầu ra: false
Giải thích: Từ trái sang phải, m trở thành d và o trở thành e, sau đó n cũng phải trở thành d. Hai chữ cái khác nhau không thể có cùng một tên, vì vậy đáp án là false.

Đầu vào: s = "r2d2"t = "c3p3"
Đầu ra: true
Giải thích: r trở thành c, 2 trở thành 3 và d trở thành p. Chữ số cũng là ký tự, và cả hai 2 đều trở thành 3.

Câu hỏi mở rộng

Khi có một danh sách từ, bạn có thể nhóm những từ đẳng cấu với nhau mà không cần so sánh từng cặp từ không?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Việc đổi tên phải hoạt động theo cả hai chiều: mỗi ký tự của s chuyển thành một ký tự của t, và mỗi ký tự của t bắt nguồn từ một ký tự của s. Hai ánh xạ, mỗi ánh xạ cho một chiều, kiểm tra cả hai trong một lượt duyệt.

So sánh từng cặp vị trí

Đúng, nhưng không chạy xong với các test lớn nhất

Ý tưởng

Phép đổi tên giữ cho các ký tự giống nhau vẫn giống nhau và các ký tự khác nhau vẫn khác nhau. Vì vậy, với mọi cặp vị trí i và j, s[i] == s[j] phải cho kết quả giống với t[i] == t[j]. Điều đó cũng đủ: nếu mọi cặp đều khớp, việc đổi mỗi ký tự trong s thành ký tự tương ứng tại vị trí đó trong t được xác định rõ và không bao giờ gán cùng một tên cho hai ký tự. Trong moon và deed, vị trí 0 và 3 chứa các chữ cái khác nhau trong s nhưng lại chứa hai chữ d trong t, nên kết quả là false.

Có khoảng n²/2 cặp: 2 × 10^8 phép so sánh khi n = 2 × 10^4, nếu không có cặp nào khiến vòng lặp dừng sớm.

Thuật toán

Lặp qua từng chỉ số i, rồi với mỗi chỉ số đó, lặp qua mọi chỉ số phía sau j.
Xác định xem s[i] có bằng s[j] hay không, và t[i] có bằng t[j] hay không.
Nếu hai kết quả khác nhau, trả về false.
Sau cặp cuối cùng, trả về true.

def isIsomorphic(s, t):
    n = len(s)
    for i in range(n):
        for j in range(i + 1, n):
            # Two positions must hold equal characters in s exactly when they do in t
            if (s[i] == s[j]) != (t[i] == t[j]):
                return False
    return True

Hai bản đồ, mỗi bản đồ cho một hướng

Ý tưởng

Hãy tạo phép đổi tên khi đọc từng ký tự. Bản đồ sToT ghi lại mỗi ký tự của s đã biến thành ký tự nào, còn tToS ghi lại mỗi ký tự của t bắt nguồn từ đâu. Ở vị trí i, với a = s[i] và b = t[i], hoặc cả hai đều mới và bạn liên kết chúng với nhau, hoặc chúng phải sẵn có và trỏ đến nhau.

Chỉ một bản đồ là chưa đủ. Chỉ dùng sToT, moon và deed sẽ vượt qua, vì không có chữ cái nào của s được đổi thành hai cách khác nhau. Vấn đề là cả m và n đều biến thành d, và ở vị trí 3, tToS đã cho biết d bắt nguồn từ m.

Mỗi vị trí cần một vài thao tác với bản đồ, nên độ phức tạp thời gian là O(n). Mã ký tự đều nhỏ hơn 128, vì vậy mỗi bản đồ có thể là một mảng gồm 128 phần tử: độ phức tạp không gian là O(1). Các phiên bản R và Swift trước tiên sao chép chuỗi vào các mảng mã ký tự, việc này cần O(n).

Thuật toán

Tạo hai từ điển rỗng, sToT và tToS.
Với mỗi chỉ số i, đặt a = s[i] và b = t[i].
Nếu a chưa có trong sToT và b chưa có trong tToS, ánh xạ a thành b và b thành a.
Nếu không, nếu sToT[a] không phải là b hoặc tToS[b] không phải là a, trả về false.
Sau chỉ số cuối cùng, trả về true.

def isIsomorphic(s, t):
    s_to_t = {}  # the character of t that each character of s became
    t_to_s = {}  # the character of s that each character of t came from
    for a, b in zip(s, t):
        if a not in s_to_t and b not in t_to_s:
            s_to_t[a] = b
            t_to_s[b] = a
        elif s_to_t.get(a) != b or t_to_s.get(b) != a:
            return False  # a already has another target, or b another source
    return True

Lỗi thường gặp và trường hợp biên

Duy trì một ánh xạ từ s sang t. Cách này chấp nhận moon và deed, cũng như ab và aa.
So sánh số lần xuất hiện của từng ký tự. abcabc và xyzxzy đều dùng ba ký tự, mỗi ký tự xuất hiện hai lần, nhưng chữ b thứ hai nằm ở vị trí của z, trong khi chữ b thứ nhất nằm ở vị trí của y.
Coi chữ hoa và chữ thường là như nhau. aA chứa hai ký tự khác nhau, nên không thể biến thành bb.
Chỉ định kích thước các mảng ánh xạ cho các chữ cái từ a đến z. Chữ hoa và chữ số nằm ngoài phạm vi đó; hãy dùng mã ký tự đầy đủ làm chỉ số với 128 phần tử.

Câu hỏi thường gặp4

Độ phức tạp thời gian của chuỗi đẳng cấu là bao nhiêu?

Lời giải dùng hai ánh xạ đọc mỗi vị trí một lần, nên có độ phức tạp thời gian O(n). Các ánh xạ chứa tối đa một mục cho mỗi ký tự có thể có, gồm 62 chữ cái và chữ số, nên độ phức tạp không gian phụ là O(1). So sánh mọi cặp vị trí cần O(n²).

Tại sao bạn cần hai bảng băm cho các chuỗi đẳng cấu?

Ánh xạ từ s sang t phát hiện một ký tự trong s được đổi tên thành hai ký tự khác nhau. Nó không phát hiện được hai ký tự trong s được đổi tên thành cùng một ký tự, như trong ab và aa. Ánh xạ từ t ngược lại s phát hiện trường hợp đó.

Phép đẳng cấu có tính đối xứng không?

Đúng vậy. Phép đổi tên một-một có thể đảo ngược, vì vậy nếu s được đổi tên thành t, đảo ngược mọi tên sẽ đổi t trở lại thành s. isIsomorphic(s, t) và isIsomorphic(t, s) luôn cho kết quả giống nhau.

Làm cách nào khác để kiểm tra xem hai chuỗi có đẳng cấu hay không?

Thay mỗi ký tự bằng vị trí xuất hiện đầu tiên của ký tự đó rồi so sánh kết quả. noon và deed đều trở thành 0 1 1 0, trong khi moon trở thành 0 1 1 3. Thuật toán cũng chạy trong thời gian O(n) và dùng bộ nhớ O(n) cho hai mẫu.

def isIsomorphic(s, t):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

s = "noon"
t = "deed"

Đầu ra mong đợi

true