Javascript - лучшее решение для поиска анаграмм - сложность времени O (n log n)

Question

ОТКАЗ ОТ ОТВЕТСТВЕННОСТИ

Привет всем, я понимаю, что есть несколько вопросов / ответов по Javascript, которые касаются выяснения того, как найти, если два слова являются анаграммами.

Я не просто ищу функцию, которая выясняет, являются ли два слова / строки анаграммами.Я ищу функцию, которая будет быстрее, чем приведенная ниже.В настоящее время я считаю, что временная сложность функции, представленной ниже, составляет O (n log n) .

Я хотел бы выяснить функцию, которая имеет временную сложность O(n) или что-то, что имеет время выполнения, которое быстрее, чем предоставленное.

КОД

const isAnagram = (str1, str2) => {

  str1 = str1.toLowerCase();
  str2 = str2.toLowerCase();


  if (str1.length !== str2.length) {
     return false
  }

  let sortStr1 = str1.split('').sort().join('').trim();
  let sortStr2 = str2.split('').sort().join('').trim();

  return sortStr1 === sortStr2
 };

console.log(isAnagram('dog', 'goD')); //true

Answer 1

Вы можете попробовать подсчитать алгоритм на основе.

const isAnagram = (str1, str2) => {

  str1 = str1.toLowerCase();
  str2 = str2.toLowerCase();
  //and remove any char you think not important (like space) here
  
  if (str1.length !== str2.length) return false
  
  let counting = {}
  for(let c of str1) 
     if(counting[c]) ++counting[c]
     else counting[c] = 1
  
  for(let c of str2)
     if(counting[c]) --counting[c]
     else return false
  
  return true
};

console.log(isAnagram('dog', 'goD')); //true
console.log(isAnagram('eleven plus two', 'twelve plus one')); //true
console.log(isAnagram('dog', 'hot')); //false
console.log(isAnagram('banana', 'nana')); //false

Answer 2

Вот еще одна возможная идея, которая исходит от: Алгоритм нахождения анаграмм и основана на фундаментальной теореме арифметики , которая гласит:

Каждое целое число больше 1 либо является простым числом, либо может быть представлено как произведение простых чисел, и, кроме того, это представление является уникальным, вплоть до (за исключением) порядка факторов.

Итак, если мы назначим каждую букву в алфавите простому числу, а затем вычислим произведение этих чисел, это число будет уникальным (из-за фундаментальной теоремы арифметики). Это означает, что для мультимножества букв произведение простых чисел для каждой буквы в этом мультимножестве является уникальным. Затем, если два слова или предложения имеют одинаковое число, эти два слова или предложения являются анаграммами друг друга.

Реализация:

let letters = {"a":2, "b":3, "c":5, "d":7, "e":11, "f":13, "g":17, "h":19, "i":23, "j":29, "k":31, "l":37, "m":41, "n":43, "o":47, "p":53, "q":59, "r":61, "s":67, "t":71, "u":73, "v":79, "w":83, "x":89, "y":97, "z":101};

const isAnagram = (str1, str2) =>
{
    str1 = str1.toLowerCase();
    str2 = str2.toLowerCase();            
    let repStr1 = 1, repStr2 = 1;

    for (let i = 0; i < Math.max(str1.length, str2.length); i++)
    {
        repStr1 *= (str1[i] && letters[str1[i]]) ? letters[str1[i]] : 1;
        repStr2 *= (str2[i] && letters[str2[i]]) ? letters[str2[i]] : 1;
    }

    return (repStr1 === repStr2);
};

console.log("[dog, goD] Anagrams?", isAnagram('dog', 'goD'));
console.log("[dogo, goD] Anagrams?", isAnagram('dogo', 'goD')); 
console.log("[Roast Beef, Eat for BSE] Anagrams?", isAnagram('Roast Beef', 'Eat for BSE'));

.as-console {background-color:black !important; color:lime;}
.as-console-wrapper {max-height:100% !important; top:0;}

Преимущества

• Принимает анаграммы различной длины (см. Третий пример).
• Is O(n) (требуется только одна петля).

Недостатки

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