Группировка с хеш-картой

Проблема, которую мы решаем:

Тебе дан массив слов [“eat”, “tea”, “ate”, “bat”, “tab”] и попросили: сгруппируй все анаграммы вместе.

Один подход: вложенные циклы и проверки анаграмм.

function groupAnagramsNaive(words) {
  const groups = [];
  const used = new Array(words.length).fill(false);
  
  for (let i = 0; i < words.length; i++) {
    if (used[i]) continue;
    
    const group = [words[i]];
    used[i] = true;
    
    // Для каждого слова, проверь все остальные слова
    for (let j = i + 1; j < words.length; j++) {
      if (!used[j] && areAnagrams(words[i], words[j])) {
        group.push(words[j]);
        used[j] = true;
      }
    }
    
    groups.push(group);
  }
  
  return groups;
}

function areAnagrams(s, t) {
  if (s.length !== t.length) return false;
  const sorted1 = s.split('').sort().join('');
  const sorted2 = t.split('').sort().join('');
  return sorted1 === sorted2;
}

Это O(n² · m log m), где n это количество слов, m это средняя длина слова.

Идея приёма группировки:

Вместо этого используй хеш-карту, где значение это список, не счёт. Для каждого слова вычисли его ключ группировки (буквы отсортированы), затем добавь его в список под этим ключом.

function groupAnagrams(words) {
  const map = new Map();  // ключ → [список слов]
  
  for (let word of words) {
    // Вычисли ключ группировки: отсортированные буквы
    const key = word.split('').sort().join('');
    
    // Добавь это слово в список под этим ключом
    if (!map.has(key)) {
      map.set(key, []);
    }
    map.get(key).push(word);
  }
  
  // Вернуть все группы
  return Array.from(map.values());
}

// Пример: ["eat", "tea", "ate", "tan", "nat"]
// "eat" → ключ "aet" → map["aet"] = ["eat"]
// "tea" → ключ "aet" → map["aet"] = ["eat", "tea"]
// "ate" → ключ "aet" → map["aet"] = ["eat", "tea", "ate"]
// "tan" → ключ "ant" → map["ant"] = ["tan"]
// "nat" → ключ "ant" → map["ant"] = ["tan", "nat"]
// Результат: [["eat", "tea", "ate"], ["tan", "nat"]]

Один цикл, O(n · m log m) время (n слов, каждое занимает m log m для сортировки и хеша). Одна хеш-карта, O(n) память.

Почему это работает:

• Одинаковый ключ, одна группа: все анаграммы слова имеют одинаковые отсортированные буквы, поэтому они вычисляют одинаковый ключ и попадают в одно ведро.
• Порядок не важен: если “aet” приходит раньше “ate”, они оба отображают на “aet” и объединяются в один список.
• Один проход: пока ты итерируешь, предметы, что принадлежат вместе, сталкиваются нарочно под одним ключом.

Форма группировки:

Приём это: для каждого предмета: ключ = f(предмет); map[ключ].push(предмет).

Дизайн ключа это сердце группировки. Правильный ключ делает предметы, что должны быть вместе, сталкивающимися:

• Анаграммы: ключ = отсортированные буквы. “eat”, “tea”, “ate” все отображают на “aet”.
• Группы остатка: ключ = n % k. Числа 5, 11, 17 с k=6 все отображают на 5 (остаток).
• Первая буква: ключ = слово[0]. “apple”, “apricot” оба отображают на “a”.
• Возрастной диапазон: ключ = Math.floor(возраст / 10). Возрасты 23, 24, 25 все отображают на 2 (20s).
• Строка в сетке: ключ = точка.строка. Точки (3, 1), (3, 5), (3, 9) все отображают на строку 3.

Группировка vs. подсчёт частоты:

• Частота: map[ключ] это счёт (число). Сколько раз каждый ключ встречается?
• Группировка: map[ключ] это список (массив). Какие предметы отображают на этот ключ?

Частота отвечает на “сколько”. Группировка отвечает на “какие”.

Пример:

// Частота: подсчитай символы в "mississippi"
const freq = new Map();
for (let char of "mississippi") {
  freq.set(char, (freq.get(char) ?? 0) + 1);
}
// freq: m→1, i→4, s→4, p→2

// Группировка: группируй символы по значению в "mississippi"
const groups = new Map();
for (let char of "mississippi") {
  if (!groups.has(char)) groups.set(char, []);
  groups.get(char).push(char);
}
// groups: m→['m'], i→['i','i','i','i'], s→['s','s','s','s'], p→['p','p']