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

В этом посте мы рассмотрим решение проблемы групповой анаграммы Leetcode, где большая часть трудностей связана с выводом результата очень специфическим образом.

Постановка задачи проста: для группы строк в массиве сгруппируйте все анаграммы друг друга в массивы. Так, например, если у нас есть массив с именем strs (для строк) типа [«есть», «чай», «загар», «ел», «нат», «летучая мышь»], результат будет выглядеть так:

  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]

Нам не нужно беспокоиться о порядке, регистре или специальных символах. Давайте погрузимся в решение ниже

Во-первых, давайте напомним себе, что такое анаграмма: слово, которое состоит из того же количества букв, что и другое слово. Итак, как и на картинке выше, «слушать» является анаграммой слова «беззвучно».

Простой способ проверить, являются ли два слова анаграммами друг друга, - это сделать следующее:

return 
word1.split("").sort().join("") === word2.split("").sort().join("")

Используя «слушать» в качестве первого слова и «тихий» в качестве второго, этот код выполняет следующие действия:

  • Создает массив, разбивает каждый символ слова на элементы в этом массиве, разделенные ничем, и возвращает этот массив. Итак, теперь word1 - это [«l», «i», «s», «t», «e», «n»], а word2 - это [«s», «i», «l», «e», « п »,« т »]
  • Сортирует каждый элемент массива по умолчанию в порядке возрастания. Итак, теперь word1is [«e», «i», «l», «n», «s», «t»] это [«e», «i», «l», «n», «s», «Т»]
  • Объединяет все элементы массива вместе, ничто не разделяет элементы. Итак, теперь word1 - это «eilnst», а word2 - «eilnst».
  • Это одно и то же? Да! Таким образом, будет оценено значение true.

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

Теперь, когда у нас есть способ проверить, является ли слово анаграммой друг друга, все, что нам нужно сделать, это сгруппировать их определенным образом. Это более сложная часть алгоритма. Вот полное решение:

function groupAnagrams(strs) {
  let result = {};
for (let word of strs) {
    let cleansed = word.split("").sort().join("");
    if (result[cleansed]) {
      result[cleansed].push(word);
    } else {
      result[cleansed] = [word];
    }
  }
return Object.values(result);
}

Несмотря на то, что они маленькие, здесь происходит очень многое. Давайте повторим это с некоторыми из наших примеров: [«есть», «чай», «загар», «съел», «нат», «летучая мышь»];

Сначала мы инициализируем объект или хеш с именем result. Здесь мы разместим наши результаты. Затем для каждого слова (элемента) массива strs мы выполняем «очистку» слова, описанного выше, чтобы оно было готово проверить, является ли оно анаграммой. Итак, «есть» теперь «аэт».

Затем мы выполняем некоторые условные проверки, которые предназначены для подготовки наших данных в нужном нам формате. Сначала мы хотим проверить, есть ли очищенное слово уже в нашем объекте результата (т.е. это может быть анаграмма слова, которое мы уже повторили), поэтому для «aet»:

  • Если я ищу aet в объекте результата, и он возвращает значение правдиво, тогда мы просто вставляем в этот результат (который будет массивом) текущее слово, которое мы повторение (съесть).
  • Если нет, а в этом первом случае там ничего не будет, мы добавим очищенное слово в качестве ключа и исходное слово в качестве его значения в форме массива со словом («eat») в качестве его первого элемента.

Мы делаем это для каждого слова… далее «чай»

  • Мы «очищаем» его и делаем «аэт»
  • Дает ли мне истинное значение поиск значения «aet»? Оно делает! Давайте возьмем это значение (которое представляет собой массив) и вставим туда слово («чай»). Теперь объект выглядит так:
result = {
   aet: ["eat", "tea"]
}

Еще раз. Повторяем с «загаром». После очищения это «муравей». Есть ли «муравей» в хэше результата? Это не! Итак, мы добавляем очищенное слово в качестве ключа, а исходное слово в виде массива со словом («tan») внутри него в качестве первого элемента. Теперь хеш результата выглядит так:

result = {
   aet: ["eat", "tea"],
   ant: ["tan"]
}

После перебора всех слов в массиве strs хеш результата будет выглядеть так:

result = {
   aet: ["eat", "tea", "ate"],
   ant: ["tan", "nat"],
   abt: ["bat"]
}

Теперь нам просто нужно вернуть все группировки. Обратите внимание, это все значения в нашем объекте key: value. Итак, мы возвращаем его с помощью Object.values ​​(result), и все готово!

Спасибо за прочтение!

И помните: выдержка ›талант.