Анаграммы JS с использованием нотации Big O

Мы говорим, что две строки являются анаграммами друг друга, если они содержат одинаковые буквы в одинаковом количестве существования каждой буквы, независимо от неалфавитных букв и чувствительности к регистру.

Вот пример

// 'hello', 'elloh' -> anagrams
// 'love', 'hate' -> not anagrams
// 'i'm 26 years old' -> 'myeald oirs o' -> anagrams

Войти в полноэкранный режим Выйти из полноэкранного режима

Решение простое

Сначала нужно удалить все неалфавитные буквы и перевести все буквы в нижний регистр.

// 'Hello World!@# ---30..' -> 'helloworld30'

const inputString = 'Hello World!@# ---30..'
inputString.toLowerCase().replace(/[W_]+/g, ''); // returns 'helloworld30'

Вход в полноэкранный режим Выход из полноэкранного режима

W оставляет подчеркивание, короткий эквивалент для [^a-zA-Z0-9] будет [W_].

Затем нам нужно преобразовать строку в массив, отсортировать массив по алфавиту, а затем превратить его обратно в строку

// 'hello' -> ['h', 'e', 'l', 'l', 'o'] -> ['e', 'h', 'l', 'l', 'o'] -> ehllo

const inputString = 'Hello World!@# ---30..'
inputString.toLowerCase().replace(/[W_]+/g, '').split('').sort().join(''); // returns '03dehllloorw'

Войти в полноэкранный режим Выйти из полноэкранного режима

Вот окончательный код

const anagrams = (firstInput, secondInput) => {
  return (
    firstInput
      .toLowerCase()
      .replace(/[W_]+/g, '')
      .split('')
      .sort()
      .join('') ===
    secondInput
      .toLowerCase()
      .replace(/[W_]+/g, '')
      .split('')
      .sort()
      .join('')
  );
}

Вход в полноэкранный режим Выйти из полноэкранного режима

Нотация Big O
Временная сложность: O(n * Log n), поскольку мы использовали алгоритм сортировки.

Однако существуют и лучшие решения, мы также напишем другое решение

const anagrams = (firstInput, secondInput) => {
  firstInput = firstInput.toLowerCase().replace(/[W_]+/g, '');
  secondInput = secondInput.toLowerCase().replace(/[W_]+/g, '');

  if (firstInput.length !== secondInput.length) {
    return false;
  }

  const inputLetterCount = {};

  for (let i = 0; i < firstInput.length; i++) {
    const currentLetter = firstInput[i];
    inputLetterCount[currentLetter] = inputLetterCount[currentLetter] + 1 || 1;
  }

  for (let i = 0; i < secondInput.length; i++) {
    const currentLetter = secondInput[i];
    if (!inputLetterCount[currentLetter]) return false;
    else inputLetterCount[currentLetter]--;
  }

  return true;
};

Вход в полноэкранный режим Выйти из полноэкранного режима

Большая O нотация
Временная сложность: O(n)
Пространственная сложность: O(1)

Счастливое кодирование ❤