javascript - 有效的 Anagram 空间复杂度

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