M-49. Group Anagrams

Loading...LeetCode

# 0 官方解答O(MN), O(1)
# 核心思路是用一个26位的list/tuple来指示同一系列anagram. 当然这里用到了defaultdict很实用,
# 对于missing的key存在一个默认类型的value.
# 一个用法演示:
import collections
a= collections.defaultdict(list)
a[1]=2
a[2].append(3)
print(a) 
# defaultdict(<class 'list'>, {1: 2, 2: [3]})

b=collections.defaultdict(int)
print(b[2]) 
# 0
print(b)
# defaultdict(<class 'int'>, {2: 0})

# ----原题解答----
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        res = collections.defaultdict(list)
        for string in strs:
            count = [0]*26
            for char in string:
                count[ord(char)-ord('a')] += 1
            # 因为dict的key不能为mutable类型, 所以要用tuple转换(显式转换,不能直接用括号括..
            # 要写tuple(xxx))
            res[tuple(count)].append(string)
        return list(res.values())
        
# 1 暴力, TLE了
class Solution:

    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        def check_anagram(str_a, str_b):
            map_a = {}
            map_b = {}
            for char in str_a:
                map_a[char] = map_a.get(char,0) + 1
                
            for char in str_b:
                map_b[char] = map_b.get(char,0) + 1
            
            return map_b == map_a
        
        if len(strs) == 1:
            return [[strs[0]]]
        elif not strs:
            return []
        
        map_strs = {}
        map_strs[strs[0]] = [strs[0]]
        
        for i in range(len(strs)-1):
            found = False
            for char in map_strs:
                if check_anagram(char, strs[i+1]):
                    map_strs[char].append(strs[i+1])
                    found = True
                    break
            if not found:
                map_strs[strs[i+1]] = [strs[i+1]]
                        
        return list(map_strs.values())