49. Group Anagrams

Loading...LeetCode

按照anagrams来组织array中的元素，sliding window有不少这样的题，很容易想到用hash map + counter，但这边hash map key得是counter，但counter(dict)本身并不能被hash，所以需要利用小写字母这个特性，以26长度的tuple来替代dict结构。

438. Find All Anagrams in a String

但其实anagrams并不一定要用counter来判定，sort之后相同的string肯定也是anagrams，写起来简单些，代价就是把对单个string的处理时间从O(n)变成了O(nlogn)。

Counter

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        memo = collections.defaultdict(list)
        for s in strs:
            freq = [0 for _ in range(26)]
            for ch in s:
                freq[ord(ch)-ord('a')] += 1
            memo[tuple(freq)].append(s)
        return memo.values()
                

Sort

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        memo = collections.defaultdict(list)
        for s in strs:
            key = tuple(sorted(s))
            memo[key].append(s)
        return memo.values()