Valid Anagram

Bài toán

Cho hai chuỗi s và t, trả về true nếu t là một đảo ngữ (anagram) của s, và false nếu không phải.

Định nghĩa: Một Anagram là một từ hoặc cụm từ đượ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ừ hoặc cụm từ khác, thường sử dụng tất cả các chữ cái gốc chính xác một lần.

Ví dụ 1:

Input: s = "anagram", t = "nagaram"
Output: true

Ví dụ 2:

Input: s = "rat", t = "car"
Output: false

Phân Tích & Tiếp Cận

Cách 1: Sorting (Sắp xếp)

Nếu hai chuỗi là anagram của nhau, thì khi sắp xếp các ký tự theo thứ tự bảng chữ cái, chúng phải giống hệt nhau.

function isAnagram(s: string, t: string): boolean {
    if (s.length !== t.length) return false;
    
    const sortedS = s.split('').sort().join('');
    const sortedT = t.split('').sort().join('');
    
    return sortedS === sortedT;
}

• Time Complexity: $O(n \log n)$ do việc sắp xếp.
• Space Complexity: $O(n)$ hoặc $O(1)$ tùy thuộc vào implementation của sort (tuy nhiên split() tạo mảng mới nên là $O(n)$).

Cách 2: Frequency Map (Hash Map) - Khuyên dùng

Chúng ta đếm tần suất xuất hiện của từng ký tự trong chuỗi s. Sau đó duyệt qua chuỗi t và trừ dần tần suất. Nếu cuối cùng mọi giá trị đều bằng 0 (hoặc kiểm tra hợp lệ trong quá trình trừ) thì là Anagram.

Vì đề bài thường chỉ gồm các ký tự 'a'-'z', ta có thể dùng một mảng kích thước 26 thay vì Hash Map tổng quát để tối ưu hơn nữa. Nhưng Hash Map (Object/Map trong JS) là giải pháp tổng quát cho mọi bộ ký tự (Unicode).

function isAnagram(s: string, t: string): boolean {
    if (s.length !== t.length) return false;

    const count: Record<string, number> = {};

    // Bước 1: Đếm tần suất ký tự trong s
    for (const char of s) {
        count[char] = (count[char] || 0) + 1;
    }

    // Bước 2: Trừ tần suất dựa trên t
    for (const char of t) {
        if (!count[char]) {
            // Nếu ký tự này không có trong s, hoặc đã dùng hết số lượng
            return false;
        }
        count[char]--;
    }

    return true;
}

• Time Complexity: $O(n)$ - Duyệt qua s một lần và t một lần.
• Space Complexity: $O(1)$ - Vì bảng chữ cái tiếng Anh chỉ có 26 ký tự, kích thước Map không tăng theo $n$. Kể cả với Unicode thì nó cũng là hằng số giới hạn.

Kinh Nghiệm Thực Tế Frontend

1. Dữ liệu dạng Frequency: Pattern "Frequency Map" này cực kỳ phổ biến. Ví dụ: Đếm số lượng sản phẩm trong giỏ hàng, đếm số lần xuất hiện của một từ khóa trong văn bản.
2. Validation: Khi cần so sánh "nội dung" của hai tập dữ liệu không quan tâm thứ tự, hãy nghĩ ngay đến việc đưa về dạng chuẩn (Canonical Form) bằng cách sort hoặc đếm tần suất.