哈希表实现字母异位词分组的空间复杂度疑问
字母异位词分组的空间复杂度疑问
题目:给定字符串数组
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),其中m是字符串数量,n是最长字符串的长度(最坏情况所有字符串长度相同),因为字典中有O(m)个条目,每个条目占用O(n)空间。但我在NeetCode的对应题解中看到空间复杂度被标注为O(m),请问这是为什么?
我查找了多个同类问题,但都未涉及该空间复杂度的疑问,仅有一个提问和我持相同观点,但没有得到解答,因此想确认哪种结论正确。
内容的提问来源于stack exchange,提问作者chilliefiber
相关产品推荐
相关产品推荐

