Как формировать ключ для сравнения слов: сортировка символов или использование хэш-кода

Что проверяют

Понимаете ли вы разницу между ключом, который однозначно задаёт класс анаграмм, и хэш-кодом, который лишь ускоряет поиск и может совпасть у разных строк. Задача обычно звучит как «сгруппируйте анаграммы», а следом спрашивают про сложность, регистр и Юникод.

Как отвечать

Ключ должен быть одинаковым у всех анаграмм и разным у остальных слов. Варианты:

• отсортированные символы: var a = word.ToCharArray(); Array.Sort(a); var key = new string(a);, затем Dictionary<string, List<string>>. Для слова длины k это O(k log k), просто и надёжно;
• счётчик букв: если алфавит ограничен, например латиница в нижнем регистре, массив int[26] за O(k) и ключ из него строкой: для «banana» это a3b1n2. На длинных строках быстрее сортировки;
• своё сравнение: реализация IEqualityComparer<string>, где GetHashCode считается от мультимножества букв, а Equals честно сравнивает счётчики. Хэш тогда только выбирает бакет, а Dictionary всё равно проверяет равенство.

Чистый хэш-код в роли ключа не годится. Во-первых, коллизии: у суммы кодов символов совпадают «ad» и «bc», и группы молча склеятся. Во-вторых, обычный полиномиальный хэш вида hash * 31 + c зависит от порядка символов и анаграммам даёт разные значения, то есть задачу вообще не решает. В-третьих, string.GetHashCode() в современном .NET рандомизирован для каждого процесса, его нельзя сохранять или сравнивать между запусками.

Перед построением ключа нормализуйте слово: ToLowerInvariant(), удаление пробелов и знаков, при необходимости Юникод-нормализация через Normalize().

Где спотыкаются

Кладут в словарь int-хэш вместо строки-ключа. На тесте из пяти слов всё работает, на словаре в сто тысяч слов в группах появляются чужие слова.

Забывают, что char это кодовая единица UTF-16. Эмодзи и другие символы из суррогатных пар при сортировке разрываются, а буква с отдельным диакритическим знаком перестаёт совпадать со своей составной формой.

Считают счётчик всегда лучше сортировки. Для слов от пяти до десяти букв сортировка крошечного массива быстрая, а обнуление int[26] плюс сборка строки-ключа может выйти не дешевле.