Выбор ответа Middle Массивы и хеш-таблицы обновлено
Группировка анаграмм: ключ
Вопрос
Группируем слова-анаграммы (только строчные латинские буквы). Какой ключ для Map даёт O(n · k), где k длина слова?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: Строка из 26 счётчиков букв, например "102...". Счётчики букв считаются за O(k), и ключ однозначно задаёт мультимножество букв.
Варианты ответа
- Строка из 26 счётчиков букв, например
"1#0#2#..."правильный ответ - Отсортированное слово
[...w].sort().join("") - Сумма кодов символов слова, например через
reduce - Произведение кодов символов слова как число
Разбор
Счётчики букв считаются за O(k), и ключ однозначно задаёт мультимножество букв. Итого O(n · k).
- Сортировка корректна, но стоит O(k log k) на слово: O(n · k log k).
- Сумма кодов неуникальна: у
"ad"и"bc"она одинакова. - Произведение тоже даёт коллизии и быстро переполняет точность Number.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.