Mô tả bài toán

Cho hai chuỗi s và t, hãy viết một hàm để xác định xem t có phải là một từ đảo chữ cái (anagram) của s hay không.

Từ đảo chữ cái: Một từ đảo chữ cái được hình thành bằng cách sắp xếp lại các chữ cái của một từ khác, sử dụng chính xác tất cả các chữ cái gốc chỉ một lần.

Ví dụ 1:

• Đầu vào: s = "anagram", t = "nagaram"
• Đầu ra: true

Ví dụ 2:

• Đầu vào: s = "rat", t = "car"
• Đầu ra: false

Ghi chú

• 1 <= s.length, t.length <= 5 * 104
• s và t chỉ chứa các chữ cái tiếng Anh viết thường.

Phương pháp 1: Sắp xếp

Để xác định xem hai chuỗi có phải là từ đảo chữ cái của nhau hay không, một phương pháp trực quan là sắp xếp các ký tự trong cả hai chuỗi và sau đó so sánh chúng. Nếu hai chuỗi là từ đảo chữ cái, chúng phải chứa cùng một tập hợp các ký tự với cùng tần suất, do đó, khi được sắp xếp theo cùng một thứ tự, chúng sẽ trở nên giống hệt nhau.

Phương pháp này bao gồm hai bước chính:

1. Kiểm tra độ dài: Nếu độ dài của hai chuỗi khác nhau, chúng không thể là từ đảo chữ cái.
2. Sắp xếp và so sánh: Sắp xếp các ký tự của cả hai chuỗi và kiểm tra xem kết quả có bằng nhau hay không.

Dưới đây là triển khai bằng Python:

class AnagramValidator:
    def check_if_anagram(self, text1: str, text2: str) -> bool:
        # Bước 1: Kiểm tra độ dài của hai chuỗi.
        # Nếu chúng không bằng nhau, text2 chắc chắn không thể là từ đảo chữ cái của text1.
        if len(text1) != len(text2):
            return False
        
        # Bước 2: Sắp xếp các ký tự trong mỗi chuỗi.
        # Sau đó, nối các ký tự đã sắp xếp lại thành chuỗi và so sánh.
        # Nếu hai chuỗi là từ đảo chữ cái, chuỗi đã sắp xếp của chúng sẽ giống hệt nhau.
        sorted_text1 = "".join(sorted(text1))
        sorted_text2 = "".join(sorted(text2))
        
        return sorted_text1 == sorted_text2

Phân tích hiệu suất (Phương pháp sắp xếp)

Mặc dù phương pháp sắp xếp đơn giản và dễ hiểu, nhưng nó có một nhược điểm về hiệu suất. Hoạt động sắp xếp chuỗi với độ dài N thường có độ phức tạp thời gian là O(N log N). Với các ràng buộc của bài toán cho phép chuỗi dài tới 5 * 10^4 ký tự, độ phức tạp O(N log N) có thể khá tốn kém, dẫn đến thời gian chạy không tối ưu.

Câu hỏi đặt ra là liệu chúng ta có thể đạt được hiệu suất tốt hơn mà không cần phải sắp xếp toàn bộ chuỗi hay không?

Phương pháp 2: Đếm tần suất ký tự

Để cải thiện hiệu suất, chúng ta có thể áp dụng phương pháp đếm tần suất ký tự. Ý tưởng cốt lõi là nếu hai chuỗi là từ đảo chữ cái, chúng phải chứa chính xác cùng một tập hợp các ký tự với cùng số lần xuất hiện cho mỗi ký tự. Ví dụ, nếu chuỗi s có ba chữ 'a', thì chuỗi t cũng phải có ba chữ 'a'.

Vì bài toán quy định rằng các chuỗi chỉ chứa các chữ cái tiếng Anh viết thường (từ 'a' đến 'z'), chúng ta biết rằng chỉ có 26 ký tự có thể có. Điều này cho phép chúng ta sử dụng hai mảng (hoặc danh sách trong Python) có kích thước 26 để theo dõi số lần xuất hiện của mỗi ký tự trong cả hai chuỗi s và t.

Các bước thực hiện:

1. Kiểm tra độ dài: Tương tự như phương pháp sắp xếp, nếu độ dài khác nhau, chúng không phải là từ đảo chữ cái.
2. Khởi tạo mảng đếm: Tạo hai mảng kích thước 26, được khởi tạo bằng 0, để lưu trữ số lần xuất hiện của các ký tự cho s và t.
3. Đếm tần suất: Duyệt qua cả hai chuỗi đồng thời. Đối với mỗi ký tự, tính chỉ số tương ứng trong mảng đếm (ví dụ: 'a' tương ứng với chỉ số 0, 'b' với chỉ số 1, v.v.) và tăng giá trị tại chỉ số đó lên 1.
4. So sánh mảng đếm: Sau khi duyệt xong cả hai chuỗi, so sánh hai mảng đếm. Nếu chúng giống hệt nhau, thì hai chuỗi là từ đảo chữ cái.

Dưới đây là triển khai bằng Python:

class AnagramProcessor:
    def check_anagram_by_counts(self, primary_str: str, secondary_str: str) -> bool:
        # Bước 1: Kiểm tra độ dài.
        # Nếu độ dài không bằng nhau, hai chuỗi không thể là từ đảo chữ cái của nhau.
        if len(primary_str) != len(secondary_str):
            return False
        
        # Bước 2: Khởi tạo hai mảng để lưu trữ tần suất xuất hiện của 26 chữ cái tiếng Anh.
        # Mỗi phần tử trong mảng tương ứng với một chữ cái từ 'a' đến 'z'.
        counts_for_primary = [0] * 26
        counts_for_secondary = [0] * 26
        
        # Bước 3: Duyệt qua các chuỗi và đếm tần suất.
        # Đối với mỗi ký tự, chúng ta tính chỉ số bằng cách trừ mã ASCII của 'a'.
        for i in range(len(primary_str)):
            # Tăng bộ đếm cho ký tự hiện tại trong primary_str
            counts_for_primary[ord(primary_str[i]) - ord('a')] += 1
            # Tăng bộ đếm cho ký tự hiện tại trong secondary_str
            counts_for_secondary[ord(secondary_str[i]) - ord('a')] += 1
            
        # Bước 4: So sánh hai mảng đếm.
        # Nếu hai mảng giống hệt nhau, điều đó có nghĩa là mỗi ký tự xuất hiện 
        # cùng số lần trong cả hai chuỗi, chứng tỏ chúng là từ đảo chữ cái.
        return counts_for_primary == counts_for_secondary

Phân tích độ phức tạp (Phương pháp đếm tần suất)

• Độ phức tạp thời gian: O(N), trong đó N là độ dài của chuỗi. Chúng ta chỉ cần một lần duyệt qua mỗi chuỗi để đếm tần suất ký tự.
• Độ phức tạp không gian: O(1). Chúng ta sử dụng hai mảng có kích thước cố định là 26 (số lượng chữ cái trong bảng chữ cái tiếng Anh). Kích thước này không phụ thuộc vào độ dài của chuỗi đầu vào, do đó được coi là không gian hằng số.