Дано две строки. Нужно определить является ли одна строка анаграммой другой.
По определению, анаграмма — перестановка букв в слове, что в результате даёт другое слово. Надо удостовериться, что количество букв в первом слове соответствует количеству тех же букв в другом слове.
Как посчитать количество букв? Можно, не особо задумываясь, завести словарь где ключами являются буквы, а значениями — их количество.
const counters = {};
for (let i = 0; i < s.length; i++) {
counter[s[i]] = counter[s[i]] ? counter[s[i]] + 1 : 1;
}
Однако, по-моему, имеет смысл посмотреть как можно решить задачу без использования словаря, имея только массив, это же поможет понять как вообще реализован словарь.
В памяти компьютера нет никаких букв, а есть только числа (двоичные), так как же представлены буквы? Ответ — с помощью кодировки, т.е. таблицы соответствия символов некоторым числам.
Чтобы не вдаваться в детали различных кодировок (ASCII, UTF-8 vs UTF-16) и как работать с юникодом в JavaScript, можно допустить, что мы работает только со строчными символами английского алфавита (имеет смысл уточнить у интервьюера, что определённо накинет пару очков в карму 😉), т.е. в рамках ASCII.
<aside> 💡 Любопытно про Unicode в JavaScript, например, согласно ECMAScript (спецификации языка) каждый символ в строке закодирован в UTF-16.
</aside>
В JavaScript есть специальный метод строки, которые по индексу символа в строке возвращается его числовой код.
// 97
'a'.charCodeAt(0)
// 122
'z'.charCodeAt(0)
Итак, кажется, всё готово для того, чтобы понять как решить задачу с использованием только массива — в английском алфавите всего 26 символов и мы знаем их числовые коды, что позволяет вычислить индекс каждого символа в массиве.
// 97 → начало отсчёта, т.е. позиция буквы "a"
arr[s.charCodeAt(i) - 97]
По-моему, довольно любопытное упражнения, чтобы понять как реализован словарь и почему в обычном JavaScript-объекте в качестве ключей могут быть только строки.
Каждый ключ (сперва будет преобразован в строку) подаётся на вход хэш-функции задача которой, принимая на вход строку — вернуть индекс в массиве (т.е. число в определённом диапазоне) таким образом, чтобы максимально равномерно заполнить массив.
Учитывая, что ключей может быть сколько угодно много, а массив определённой длины — неизбежны коллизии, поэтому значениями в таком массиве являются другие массивы, хранящие пары ключ-значение, так что можно пробежаться по массиву и найти все-таки значение соответствующее указанному ключу.
Хэш-таблицы и ассоциативные массивы — отдельная тема в Computer Science, не возьму на себя смелость говорить об этом подробнее, однако, любопытно в общих чертах представлять как это работает.
Вернёмся к нашим счётчикам и анаграммам, решение задачи: