Как определить, является ли строка анаграммой Javascript

Как определить, является ли строка анаграмой Javascript

При прохождении собеседования как разработчик JavaScript (js/front end) вам могут задавать задачки, которые будут показывать ход ваших мыслей и соображалку. В текущий момент я хотел бы рассказать про задачу по определению того, является ли одно слово анаграмой для другого слова.

Постановка задачи с анаграммами

Чтобы понимать, как правильно решить задачу — нужно понимать ее условия и что от нас требуется. Итак, начнем.

Что такое анаграмма ? Одно слово можно считать анаграммой другого слова в том случае, если мы можем переставить его буквы таким образом, что получим второе слово.

Тестовые примеры:

  • слова ‘silent’ и ‘listen’ являются анаграммами
  • слова ‘foo’ и ‘bar’ НЕ являются анаграммами

Решение задачи на JavaScript (JS)

Естественно, что здесь может быть масса вариантов реализации. Самым простым был бы такой алгоритм: вы превращаете строки в массивы (.split(»)) и сортируете массивы. После этого, вам нужно просто сравнить полученные отсортированные массивы. Если они равны, то оба слова являются анаграммами друг друга.

Более продуманным будет сделующее решение:

function areAnagrams(w1, w2) {
const charCount = new Map();
for (const c of w1.split(»)) {
charCount.set(c, (charCount.get(c) || 0) + 1);
}
for (const c of w2.split(»)) {
if (!charCount.has(c))
return false;
charCount.set(c, charCount.get(c) — 1);
}
return Array.from(charCount.values()).every(v => v === 0);
}

А теперь, пройдемся пошагово по предложенному коду решения.

Для начала, мы создаем коллекцию вида «ключ-значение». Здесь у нас будет лежать каждый встречаемый символ в первом слове (ключ) и количество раз этот символ повторяется в слове (значение). Для этого прекрасно подойдет такая колекция в js как Map.

Далее мы проходимся по первому слову и переносим все символы и их количество в нашу колекцию.

Затем мы начинаем проходится по всем символам второго слова и выполнять декремент для значений. Если же какой-то символ из второй строки не встречается в коллекции, то наши слова уже не равны и мы возвращаем false.

После того, как по всем словам мы прошлись и уже пообновляли количество этих символов в словах — мы должны пройтись по всей колекции и проверить, что количество символов в обоих словах одинаково.

Таким образом мы получаем асимптотическую сложность данного решения приблизительно равную O(2n). Т.е. мы проходимся по двум словам, выполняя какое-то действие над каждым символом из этих слов.


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

Кстати, не забывайте читать и другие статьи на моем блоге. Здесь я затрагиваю разные темы — от выбора фотоаппарата (я писал про sony a6000) до статей про жизненные этапы компонента в React. Ну а вообще, изначально этот блог задумывался как блог о путешествиях — так что тут же вы можете посмотреть и про путешествие к дворцу Пена, и про пляжи Унаватуны, и про собор святого Марка в Венеции.

Так что не стесняйтесь смотреть и другие статьи, а не только про решение задачки с анаграммой на javascript.