Сгруппировать список строк по анаграммам
Дан список строк. Сгруппируйте те, что являются анаграммами друг друга (одни буквы в любом порядке), в подсписки. Верните список этих групп; порядок групп не важен.
Примеры: ["eat","tea","tan","ate","nat","bat"] → [["bat"],["nat","tan"],["ate","eat","tea"]]; [""] → [[""]]; ["a"] → [["a"]].
def group_anagrams(strs: list[str]) -> list[list[str]]:
# ваш код здесьНапишите реализацию.
Раскладывают строки в словарь по канонической сигнатуре, общей для всех анаграмм. Подходит кортеж отсортированных символов tuple(sorted(s)) (или кортеж из 26 счётчиков букв — O(n) на строку вместо O(n log n)).
- ✗Группировать по длине, смешивая не-анаграммы
- ✗Ключевать по первой букве или сумме ASCII — даёт коллизии
- ✗Использовать O(n^2) попарное сравнение вместо ключа
- →Почему ключ-счётчик букв быстрее сортировки на строку?
- →Как ведёт себя случай пустой строки с вашим ключом?
All anagrams of a word share a canonical signature. Use it as a dict key and append each string to the matching bucket.
from collections import defaultdict
def group_anagrams(strs: list[str]) -> list[list[str]]:
buckets = defaultdict(list)
for s in strs:
key = tuple(sorted(s)) # or a 26-length letter-count tuple
buckets[key].append(s)
return list(buckets.values())"eat", "tea", "ate" all sort to ('a','e','t'), so they land in one bucket; "tan" and "nat" share ('a','n','t'); "bat" is alone. The empty string keys to () and forms its own group. Sorting is O(k log k) per string of length k; a letter-count tuple makes it O(k).
