有效的字谜空间复杂度

Question

var isAnagram = function(s, t) {
const len = s.length;
if (len !== t.length) return false;
const hashTab = {};
for (let i = 0; i < len; i++) {
    if (!hashTab[s[i]]) {
        hashTab[s[i]] = 1;
    } else {
        hashTab[s[i]]++;
    }
    if (!hashTab[t[i]]) {
        hashTab[t[i]] = -1;
    } else {
        hashTab[t[i]]--;
    }
}
for (let item in hashTab) {
    if (hashTab[item]) return false;
}
return true;

很难计算出该算法的空间复杂度。我的假设是 O(n)，因为哈希表的大小随着输入 s 的增加而增加。本题假设字符串只包含小写字母。

Answer 1

正如您提到的，字符串仅包含小写字母，我们可以将给定字符串中的字符转换为相应的整数，范围从0到25。
为了跟踪这些字母的出现频率，我们可以声明一个大小正好为 26 的空间数组。因此，总体空间复杂度将为 O(M)，其中 M 是不同字母的总数。在这种情况下，M=26。所以，空间复杂度是 O(26)。

var isAnagram = function(s, t) {
  const len = s.length;
  if (len !== t.length) return false;
  hashTab = new Array(26);
  for(i = 0; i<26; i++){
     hashTab[i] = 0;
  }
  for (let i = 0; i < len; i++) {
     idx = s[i].charCodeAt()-97; 
     hashTab[ idx ]++;
     idx = t[i].charCodeAt()-97; 
     hashTab[ idx ]--;
  }
  for(i = 0; i<26; i++){
     if(hashTab[i]!=0) return false;
  }
  return true;
}

Answer 2

代码中的主要空间成本是哈希映射，它可能包含从

a

到

z

的每个小写字母的频率计数器。所以在这种情况下，空间复杂度应该是恒定的

O(26)

。

更一般地说，这个问题的空间复杂度与输入字符串的字母大小有关。如果输入字符串仅包含 ASCII 字符，那么在最坏的情况下，您的空间成本将是

O(256)

。如果字母表增长到 UNICODE 集合，那么在最坏的情况下空间复杂度会差很多。

所以总的来说是

O(size of alphabet)

。

Answer 3

由于使用的空间是恒定的（在本例中为 26 个字母/项目 - 或者即使您使用了 256 个项目的数组）并且不依赖于输入的长度，因此空间复杂度为 O(1)。

另请参阅此答案。

Answer 4

时间复杂度： O(n)

空间复杂度： O(n)

/**
 * @param {string} str1
 * @param {string} str2
 * @return {boolean}
 */
const isAnagram = (str1, str2) => {
    if(str1.length != str2.length) return false;
    
    const arr1 = str1.split('');
    const arr2 = str2.split('');
    let obj = {};
    
    for(let val of arr1) {
        obj[val] = ++obj[val] || 1;
    }
    
    for(let val of arr2) {
        if(!obj[val]) return false;
        else obj[val] -=1;
    }
    return true;
};