Group Anagrams

Bài toán

Cho một mảng các chuỗi strs, hãy nhóm các đảo ngữ (anagrams) lại với nhau. Bạn có thể trả về câu trả lời theo bất kỳ thứ tự nào.

Ví dụ:

Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

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

Cách 1: Sorting Key (Dùng chuỗi đã sắp xếp làm Key)

Mọi chuỗi Anagram khi sắp xếp ký tự theo bảng chữ cái sẽ trở thành một chuỗi giống hệt nhau. Ví dụ: "eat", "tea", "ate" -> Sắp xếp thành "aet".

Ta có thể dùng chuỗi đã sắp xếp này làm Key trong một Hash Map, và Value là danh sách các từ gốc.

function groupAnagrams(strs: string[]): string[][] {
    const map = new Map<string, string[]>();

    for (const s of strs) {
        // Tạo key bằng cách sort các ký tự
        const key = s.split('').sort().join('');
        
        if (!map.has(key)) {
            map.set(key, []);
        }
        map.get(key)!.push(s);
    }

    return Array.from(map.values());
}

• Time Complexity: $O(m \cdot n \log n)$ - Trong đó $m$ là số lượng chuỗi, $n$ là độ dài trung bình của mỗi chuỗi. $n \log n$ là chi phí sắp xếp mỗi chuỗi.
• Space Complexity: $O(m \cdot n)$ - Để lưu trữ Map.

Cách 2: Frequency Count Key (Kỹ thuật nâng cao)

Thay vì sort ($O(n \log n)$), ta có thể đếm tần suất ký tự ($O(n)$) để tạo ra một Key đại diện duy nhất. Vì chỉ có các ký tự 'a'-'z', ta có thể dùng một mảng đếm 26 phần tử. Ví dụ: "eat" -> 1a, 1e, 1t -> Key string dạng: "1#0#0#0#1#...#1..." (số lượng chữ cái a, b, c...).

function groupAnagrams(strs: string[]): string[][] {
    const map = new Map<string, string[]>();

    for (const s of strs) {
        // Tạo mảng đếm 26 ký tự (a-z)
        const count = new Array(26).fill(0);
        
        for (const char of s) {
            // ASCII của 'a' là 97
            count[char.charCodeAt(0) - 97]++;
        }

        // Biến mảng đếm thành string key unique
        // Dùng dấu phân cách '#' để tránh nhầm lẫn 
        // (vd: 1 và 11 vs 11 và 1)
        const key = count.join('#');

        if (!map.has(key)) {
            map.set(key, []);
        }
        map.get(key)!.push(s);
    }

    return Array.from(map.values());
}

• Time Complexity: $O(m \cdot n)$ - Ta chỉ duyệt mỗi chuỗi 1 lần để đếm, không cần sort. Nhanh hơn Cách 1 khi $n$ (độ dài chuỗi) lớn.
• Space Complexity: $O(m \cdot n)$.

Pattern Nhận Diện

Khi cần nhóm các đối tượng (Group By) dựa trên một đặc tính chung nào đó:

1. Xác định đặc tính chung (Invariant) của nhóm là gì? (Ở đây là: cùng số lượng mỗi ký tự).
2. Biến đặc tính đó thành một Key có thể băm được (String/Number).
3. Dùng Hash Map để gom nhóm.

Ứng Dụng Thực Tế

Trong Frontend, bài toán "Group By" rất phổ biến khi xử lý dữ liệu trả về từ API. Ví dụ: Nhóm các giao dịch (Transactions) theo Ngày.

• Key: Date String (DD-MM-YYYY).
• Map: { '20-10-2023': [Trans1, Trans2], '21-10-2023': [Trans3] }.