Группировка анаграмм: собрать слова с одинаковым набором букв
Реализуйте функцию group_anagrams(words).
Вход: words — список строк. Слова могут повторяться.
Выход: список групп. Два слова попадают в одну группу, если одно является перестановкой букв другого ("eat", "tea", "ate").
Порядок результата задан жёстко:
- внутри группы слова идут в том порядке, в каком встречались во входном списке; повторяющиеся слова остаются в группе по разу за каждое вхождение;
- сами группы отсортированы по возрастанию своего первого слова (обычное сравнение строк Python).
Правила:
- сравнение регистрозависимое:
"Ab"и"ab"— не анаграммы; - кратность букв значима:
"aab"и"abb"— не анаграммы.
Краевые случаи:
- пустой список даёт
[]; - одно слово даёт одну группу из одного слова.
Требование по сложности: один проход по списку со словарём. Попарно сравнивать слово с представителями всех уже собранных групп нельзя — это квадратично по числу групп.
заготовка решения
def group_anagrams(words):
# ваш код
pass