LeetCode-49字母异位词分组

题目描述

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

示例 1:

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

示例 2:

输入: strs = [""]
输出: [[""]]

示例 3:

输入: strs = ["a"]
输出: [["a"]]

提示：

• 1 <= strs.length <= 104
• 0 <= strs[i].length <= 100
• strs[i] 仅包含小写字母

题解

哈希表计数（字符串统计）

建立从字符串统计的数组到字符串的哈希表映射关系

时间复杂度O(Nk)，空间复杂度O(Nk)

class Solution(object):
    def groupAnagrams(self, strs):
        """
        :type strs: List[str]
        :rtype: List[List[str]]
        """
        mp = collections.defaultdict(list) # 哈希表

        for str in strs:
            counts = [0] * 26
            for ch in str:
                counts[ord(ch) - ord("a")] += 1
            mp[tuple(counts)].append(str) # count -> str

        return list(mp.values())

哈希表（字符串排序法)

以排序后的字符串为键，建立排序后字符串与原字符串的映射关系

时间复杂度O(Nklogk)，空间复杂度O(Nk)

class Solution(object):
    def groupAnagrams(self, strs):
        """
        :type strs: List[str]
        :rtype: List[List[str]]
        """
        res = collections.defaultdict(list)
        for str in strs:
            str_sort = "".join(sorted(str))
            res[str_sort].append(str)
            
        return list(res.values())
             

哈希表的建立方法对比

• collections.defaultdict(list)
  • 需要先导入 collections 模块，然后使用 defaultdict 类并传入 list 作为默认工厂函数来创建哈希表。例如：from collections import defaultdict，hash_table = defaultdict(list)。
  • 这种方式在创建时就指定了默认值的类型为列表，当访问不存在的键时，会自动为该键创建一个空列表作为值。

res = collections.defaultdict(list)
for str in strs:
    str_sort = "".join(sorted(str))
    res[str_sort].append(str)

如解法二中直接进行append

• {}
  • 直接使用花括号 {} 就可以创建一个空的哈希表，例如：hash_table = {}。
  • 在创建时没有指定默认值，当访问不存在的键时，会抛出 KeyError 异常。

res = {}
for str in strs:
    str_sort = "".join(sorted(str))
    if str_sort in res:
        res[str_sort].append(str)
    else:
        res[str_sort] = [str]

若使用{}需要判断键是否存在。