Group Anagrams

Средняя№49подсчёт

Дан список слов. Нужно разложить их по группам так, чтобы в каждой группе были слова из одних и тех же букв, только в другом порядке. Наш пример: [arc, stop, car, pots, rat, tops] — три группы: [arc, car], [stop, pots, tops] и [rat].

49 Group AnagramsРазбор · 1×

Пример: слова [arc, stop, car, pots, rat, tops]. Ключ слова — его буквы по алфавиту; в словаре по группе на каждый ключ.

0arc1stop2car3pots4rat5topsgroupsключ → слова—
ещё не дошлитекущее слово и его ключв группеответ

Начинаем с пустого словаря: групп пока нет

01/29
сначала · назад · пуск · шаг
Скорость
1function groupAnagrams(words):
2 groups = empty map
3 for each word in words:
4 key = sort(word)
5 if key not in groups:
6 groups[key] = empty list
7 add word to groups[key]
8 return values of groups
состояние
word
–
key
–
groups
{}
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

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

  1. У анаграмм одни и те же буквы в другом порядке. Если расставить буквы по алфавиту, все анаграммы превратятся в одну строку: и «arc», и «car» дают «acr». Эта строка и есть ключ.
  2. Словарь сразу находит группу по ключу, поэтому хватает одного прохода по словам: каждое слово не сравниваем со всеми остальными.
  3. Слово с новым ключом заводит свою группу. У «rat» анаграмм нет, и в его группе оно одно.

Сложность

Время O(n · k log k): n слов, и буквы каждого, а их k, сортируем. Если вместо сортировки считать 26 букв, ключ строится за O(k). Память O(n · k): каждое слово один раз попадает в словарь.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.