Почему это работает
- У анаграмм одни и те же буквы в другом порядке. Если расставить буквы по алфавиту, все анаграммы превратятся в одну строку: и «arc», и «car» дают «acr». Эта строка и есть ключ.
- Словарь сразу находит группу по ключу, поэтому хватает одного прохода по словам: каждое слово не сравниваем со всеми остальными.
- Слово с новым ключом заводит свою группу. У «rat» анаграмм нет, и в его группе оно одно.
Сложность
Время O(n · k log k): n слов, и буквы каждого, а их k, сортируем. Если вместо сортировки считать 26 букв, ключ строится за O(k). Память O(n · k): каждое слово один раз попадает в словарь.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗