Действительная анаграмма — Leetcode #242

На этой неделе мы проверим, являются ли два слова или фразы анаграммами. Возвращает true, если они есть, и false, если нет. Следуйте вместе с Leetcode # 242. Мы решим эту проблему с помощью 2 решений.

Слова, являющиеся анаграммами, имеют те же буквы, но переставлены в другом порядке. Например, распространенная анаграмма «слушай» и «молчи». Иногда это могут быть такие фразы, как «Джим Моррисон» и «Мр. Mojo Risin» или «анаграмма» и «пилить барана», как указано выше.

В первом решении мы удалим все знаки препинания, используя регулярное выражение и .replace, а затем преобразуем каждую строку во все строчные буквы для более точного сравнения. Затем мы разделим каждую строку, чтобы она стала массивом, отсортируем массив и объединимся, чтобы снова стать строкой. Мы не можем вызвать sort для строки напрямую, потому что sort — это метод массива.

На этом этапе они должны выглядеть одинаково, если являются анаграммами, поэтому мы можем проверить их на равенство и вернуть true или false с помощью условного тернарного оператора.

Используя в качестве примера «listen» и «silent», finalStringA и finalStringB будут выглядеть как «eilnst».

function isAnagram(stringA, stringB) {
  let lowerCaseA = stringA.replace(/[^\w]/g, "").toLowerCase()
  let lowerCaseB = stringB.replace(/[^\w]/g, "").toLowerCase()
  let finalStringA = lowerCaseA.split('').sort().join('')
  let finalStringB = lowerCaseB.split('').sort().join('')
  return finalStringA === finalStringB ? true : false
}

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

function isAnagram(stringA, stringB){
  let a = stringA.replace(/[^\w]/g, "").toLowerCase();
  let b = stringB.replace(/[^\w]/g, "").toLowerCase();
  let objA = {};
  let objB = {};
  for (let char of a) {
    objA[char] = objA[char] + 1 || 1;
  }
  for (let char of b) {
    objB[char] = objB[char] + 1 || 1;
  }
}

Далее мы проверим длину ключей каждого объекта. Если они не одинаковой длины, мы знаем, что слова не могут быть анаграммами, и можем вернуть false.

Последнее, что мы проверим, — это фактические символы в каждом частотомере. Если они не совпадают, мы знаем, что можем немедленно вернуть false.

Если мы пройдем через проверку длины и символов, это будет означать, что слова должны быть анаграммами. Поэтому мы можем вернуть true.

Вот наш окончательный результат:

function isAnagram(stringA, stringB){
  // remove non-word characters and convert to lower case
  let a = stringA.replace(/[^\w]/g, "").toLowerCase();
  let b = stringB.replace(/[^\w]/g, "").toLowerCase();
  // create frequency counters
  let objA = {};
  let objB = {};
  for (let char of a) {
    objA[char] = objA[char] + 1 || 1;
  }
  for (let char of b) {
     objB[char] = objB[char] + 1 || 1;
  }
  // check to see if object length matches
  if (Object.keys(objA).length !== Object.keys(objB).length){
     return false;
  }
  
  // iterate through object to see if char doesn't match
  for (let char in objA) {
     if (objA[char] !== objB[char]) {
        return false;
     }
  }
  // must be an anagram!
  return true;
}