免责声明
大家好,我知道很少有 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
最佳答案
您可以尝试基于计数的算法。
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
关于Javascript - 查找字谜的更好解决方案 - 时间复杂度 O (n log n),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/55822530/