使用哈希图对字谜进行分组的空间复杂度

Question

我正在解决一道leetcode问题。

问：给定一个字符串数组

strs

，将所有字谜词组合在一起 子列表。您可以按任何顺序返回输出。

注：

strs[i]

由小写英文字母组成

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        # O(m*n) time complexity
        # O(m*n) space complexity
        d = {} # O(m) entries each with O(n) size
        for s in strs: # O(m)
            s_l = [0] * 26
            for c in s: # O(n)
                s_l[ord(c) - ord("a")] += 1
            t_l = tuple(s_l) # this is O(1) entry size with O(m) tuples
            if t_l in d:
                d[t_l].append(s)
            else:
                d[t_l] = [s]
        return d.values()

所以，我认为空间复杂度是

O(m*n)

。字典中有

O(m)

个条目，每个条目都会有

O(n)

空间，其中

m

是字符串的数量，

n

是最大字符串的长度（最坏的情况是所有字符串都是相同长度）。

但是，我在https://neetcode.io/problems/anagram-groups中找到的解决方案表示空间复杂度是

O(m)

。为什么？

请注意，我发现了许多与此完全相同的问题，例如 [0] 到 [9]，但没有一个与空间复杂度有关。

0. 对字谜进行分组
1. 从字典中获取字谜列表
2. 组字谜 - LeetCode
3. LeetCode 49 组字谜
4. 在 Leetcode 中对字谜进行分组，无需排序
5. 如何将字符串中的字谜分组到数组中
6. 将所有字谜组合在一起
7. 分组字谜Leetcode问题（python）这个也使用了neetcode的解决方案。不幸的是没有提到空间复杂度
8. 组字谜算法的大O
9. 如何将给定字符串数组中的不同字谜组合在一起？

这个问题：字符串字谜分组|改进和分析时间复杂度也符合我的空间复杂度，但遗憾的是没有答案，所以我不知道谁是对的，如果我和提问者或neetcode。

Answer 1

字符串内容所使用的空间来自输入。您没有复制

d

字典中的字符串，只是引用输入字符串。所以这不被认为是算法空间复杂度的一部分。