检查列表中是否存在 Anagrams 单词的最佳复杂度是多少？

Question

如果我们考虑 O(n) 而不是 O(1) 对于 sort、slice、join、split?我认为第二个在性能方面更好。

而且，你知道我们是否可以将其写下来，使其具有更好的复杂性或性能。

这是题目：

Anagrams: 
a re-arrangement of letters that spells another word, 
for example: spot, tops, stop are anagrams. 

boolean containsAnagram(List<String> dictionary, String word)

assertTrue(containsAnagram(List.of("stop", "bus"), "pots"));
assertFalse(containsAnagram(List.of("stop", "bus"), "apple"));

并且，我在 javascript 中编写了如下代码：

const containsAnagram = (dic, str) => {
      console.log(dic, str);
      for(let i=0; i< str.length; i++){ 
          const letter = str[i];
          for(let j=0; j < dic.length ; j++ ){
              const word = dic[j];
              for(let k=0; k < word.length ; k++ ){
                  if(letter === word[k]){
                      dic[j] = word.slice(0, k) + word.slice(k+1, word.length);
                      // dic[j] is empty string and it is the end of the str , return true
                      if( dic[j] === '' && str.length === i+1 ){
                          return true;
                      }
                      break;
                  }
              }
          }
      }
      return false;
    };
console.log(containsAnagram(["stop", "bus"], "pots"));
console.log(containsAnagram(["stop", "bus"], "apple"));

如果考虑slice或substr是o(1)，基本给出O(n^3)。而实际情况是 slice 或 substr 具有 o(n).

的复杂性

所以，我用排序函数重写了它，如下：

const containsAnagram = (dic, str) => {
    console.log(dic, str);
    str = str.split('').sort().join(''); // n
    for(let j=0; j < dic.length ; j++ ){
        const word = dic[j].split('').sort().join(''); // o (n*n*n*n)
        dic[j] = word ;
        if( word === str ){
            return true;
        }
    }
    return false;
};  
console.log(containsAnagram(["s", "s1"], "sp")); // false
console.log(containsAnagram(["s", "psso1"], "spos1"));  // true

Answer 1

两者都不必要地复杂。 .sort 是 O(n log n)，而不是 O(n)，因此虽然它是一个改进，但并没有达到应有的水平。

为了降低计算复杂度并对 dic 和 str 中的每个字符精确迭代一次，创建一个函数，将字符串转换为一个对象，计算每个字符出现的次数，然后比较对象的值：

const groupStr = str => {
  const obj = {};
  for (const char of str) {
    obj[char] = (obj[char] || 0) + 1;
  }
  return obj;
};
const objsEqual = (obj1, obj2) => {
  const [keys1, keys2] = [obj1, obj2].map(Object.keys);
  if (keys1.length !== keys2.length) return false;
  return keys1.every(key1 => obj1[key1] === obj2[key1]);
};
const containsAnagram = (targets, input) => {
  const inputGrouped = groupStr(input);
  return targets.some(
    target => objsEqual(groupStr(target), inputGrouped)
  );
};

console.log(containsAnagram(["stop", "bus"], "pots"));
console.log(containsAnagram(["stop", "bus"], "apple"));

也就是说，在现实世界中，担心这类事情的计算复杂性可能不值得花时间，除非您要遍历多个巨大的字典或其他东西。计算复杂性仅在输入大到足以使现代计算机承受合理压力时才重要。

检查列表中是否存在 Anagrams 单词的最佳复杂度是多少？

What is the best complexity to check if an Anagrams word exist in a list?

javascript

algorithm

performance

time-complexity

string-matching