Структуры данных и алгоритмы. Все в отрасли говорят о них, и они могут быть очень пугающими, особенно когда их бросают в глаза во время собеседования. Поэтому я купил курс Udemy, рекомендованный другом (https://www.udemy.com/course/js-algorithms-and-data-structures-masterclass/), и начал углубляться, чтобы чувствовать себя более комфортно. с такими проблемами.

Сегодня я хочу сосредоточиться на одной конкретной стратегии, которую я изучил, чтобы выяснить, являются ли две строки анаграммами, но она также может быть полезна в любой ситуации, когда вам нужно подсчитать количество вхождений. Анаграмма — это слово или фраза, которые можно составить, переставив буквы в другом слове. Например, слово «кино» может быть образовано от слова «ледяной человек», так что эти два слова являются анаграммами.

Задача, которую мне поставили, заключалась в том, чтобы определить минимальное количество удалений, необходимых для создания двух строковых анаграмм друг друга. Стратегия, которую я изучил, заключалась в том, чтобы создать объект одной из строк со счетчиком того, сколько раз использовалась каждая буква, а затем посмотреть, существует ли такой же счетчик в другой строке. Затем подсчитайте оставшиеся буквы для удалений, которые должны произойти. Давайте погрузимся!

Сначала нам нужно создать две переменные в нашей функции. Один — это объект, который мы создадим из первой строки, а второй — количество необходимых удалений, которые мы вернем в конце. Затем нам нужно перебрать первую строку и создать объект, который присваивает каждому символу число в зависимости от того, сколько раз он встречается. Код выглядит так. Мы назначаем каждую букву в строке как ключ в нашем объекте и устанавливаем число равным либо 1, если этот ключ ранее не существовал, либо добавляем единицу к значению, если он уже существовал.

function makeAnagram(a, b) {
  let firstStringObject = {}
  let deletions = 0
  for (let i = 0; i<a.length; i++) {
    let letter = a[i]
    firstStringObject[letter] = (firstStringObject[letter] || 0) + 1
  }
}

Учитывая слово «мама», наш объект будет выглядеть как {m: 2, o: 1}. Далее нам нужно перебрать нашу вторую строку, чтобы сравнить значения. Если значение в строке не существует в объекте, нам нужно выполнить удаление и, следовательно, добавить 1 к нашему счетчику удалений. Если значение существует как ключ в нашем объекте, и число, связанное с этим ключом, больше нуля, то мы можем уменьшить это число на единицу, по существу удалив ту же букву. Наконец, если значение существует как ключ, то есть оно было в первой строке, но значение этого ключа равно 0, это означает, что больше не осталось вхождений этой буквы, и поэтому нам нужно снова добавить единицу к нашему счетчику удалений.

for (vals of b) {
  if (!firstStringObject[vals]) {
    deletions += 1
  } else if (firstStringObject[vals] > 0) {
    firstStringObject[vals] -= 1
  } else {
    deletions += 1
  }
}

Это позаботится о нашей второй строке, поэтому единственное, что осталось сделать, это проверить, остались ли какие-либо буквы в созданном нами объекте. Если это так, мы добавляем еще одно к удалениям для учета этих писем.

for (const [key, value] of Object.entries(firstStringObject)) {
  if (value > 0) {
    deletions += value
  }
}

Теперь у нас есть общее количество удалений, необходимых для того, чтобы сделать строки анаграммами друг друга, поэтому все, что осталось сделать, это вернуть удаления! Для меня это было откровением, потому что я никогда не рассматривал вариант решения этой проблемы путем создания объекта, считающего вхождения. Этот подход намного лучше и быстрее, чем вариант с вложенным циклом, и имеет временную сложность O(n). Я думаю, что чем больше я сталкиваюсь с такими проблемами, тем комфортнее мне становится, но определенно есть над чем поработать!