49. Group Anagrams

Задача

Дан массив строк. Сгруппируйте вместе анаграммы.

Решение

Решение

// Временная сложность: O(n × k), где n - количество строк, k - длина самой длинной строки
// Пространственная сложность: O(n × k) - для хранения всех строк в хеш-таблице
 
var groupAnagrams = function(strs) {
    const hash = {};
 
    // Проходим по каждому слову в массиве - O(n)
    for (const word of strs) {
        // Создаем массив из 26 нулей для подсчета частоты каждой буквы (a-z)
        const count = new Array(26).fill(0);
 
        // Подсчитываем частоту каждого символа в слове - O(k)
        for (const char of word) {
            // Преобразуем символ в индекс от 0 до 25
            // 'a' -> 0, 'b' -> 1, ..., 'z' -> 25
            const index = char.charCodeAt(0) - 'a'.charCodeAt(0);
            count[index]++;
        }
 
        // Создаем уникальный ключ из массива частот
        // Используем '#' как разделитель для избежания коллизий
        // Например: [1,0,0,0,1,0,...,1,0] -> "1#0#0#0#1#0#...#1#0"
        const key = count.join('#');
 
        // Группируем слова с одинаковым ключом (анаграммы)
        if (!hash[key]) {
            hash[key] = [word];
        } else {
            hash[key].push(word);
        }
    }
 
    // Возвращаем все группы анаграмм
    return Object.values(hash);
};
 
// Шаг 1: count = [0,0,0,...] (26 нулей)
// Шаг 2: обрабатываем 't' -> count[19]++ = [0,0,...,1,0,...]
//        обрабатываем 'e' -> count[4]++  = [0,0,0,0,1,0,...,1,0,...]
//        обрабатываем 'a' -> count[0]++  = [1,0,0,0,1,0,...,1,0,...]
// Шаг 3: key = "1#0#0#0#1#0#0#0#0#0#0#0#0#0#0#0#0#0#0#1#0#0#0#0#0#0"
// Слова "tea", "eat", "ate" дадут одинаковый ключ и попадут в одну группу