字母异位词

字母异位词分组

1、题目

image-20240201205948099

2、题解

由题意可知，字母异位词的共同特点是含有相同的字母，因此可以用哈希表存储一组字母异位词。遍历字符串，得到每个字符串所包含的标志并加入该字母异位词的列表。遍历完成后哈希表的值即为一组字母异位词列表。

解法一：排序

#官方题解
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        mp = collections.defaultdict(list)

        for st in strs:
            key = "".join(sorted(st))
            mp[key].append(st)
        
        return list(mp.values())

#自己写的
def add_dict(dictionary, key, value):
    if key not in dictionary:
        dictionary[key] = []
    dictionary[key].append(value)

    return dictionary


def group_anagrams(ip_str):
    mp = {}

    for st in ip_str:
        key = "".join(sorted(st))
        mp = add_dict(mp, key, st)

    return list(mp.values())

解法二：记数

由于互为字母异位词的两个字符串包含的字母相同，因此两个字符串中的相同字母出现的次数一定是相同的，故可以将每个字母出现的次数使用字符串表示，作为哈希表的键。

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        mp = collections.defaultdict(list)

        for st in strs:
            counts = [0] * 26
            for ch in st:
                counts[ord(ch) - ord("a")] += 1
            # 需要将 list 转换成 tuple 才能进行哈希
            mp[tuple(counts)].append(st)
        
        return list(mp.values())