Javascript - 查找字谜的更好解决方案 - 时间复杂度 O (n log n)

Javascript - Better solution for finding anagrams - Time complexity O (n log n)

免责声明

大家好,我知道很少有人 Javascript questions/answers 处理如何查找两个单词是否是字谜的问题。

我不只是在寻找一个函数来判断两个 words/strings 是否是变位词。我正在寻找一种比下面提供的函数更快的函数。目前,我相信下面函数的时间复杂度是 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

这是另一个可能的想法,来自:An Algorithm for Finding Anagrams and is based on the fundamental theorem of arithmetic,其中指出:

Every integer greater than 1 either is a prime number itself or can be represented as the product of prime numbers and that, moreover, this representation is unique, up to (except for) the order of the factors.

因此,如果我们将字母表中的每个字母都分配给一个素数,然后计算这些数字的乘积,那么这个数字将是唯一的( 因为算术基本定理)。这意味着对于一组字母,该多组中每个字母的素数乘积是唯一的。那么,如果两个单词或句子的编号相同,则这两个单词或句子是彼此的变位词。

实施:

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;}

优势

  • 接受不同长度的字谜(检查第三个例子)。
  • 就是O(n)(只需要一个循环)。

缺点

  • 不适用于大表达式,生成的数字会溢出。
  • 需要一个预定义的字典来区分字母和数字。
  • 除非扩展字典,否则不适用于包含稀有字符的表达式,但溢出会变得更加频繁。

您可以尝试基于计数的算法。

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