49. Group Anagrams

49. Group Anagram (Medium) 字母异位词分组

题干

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

Input: strs = [“eat”,“tea”,“tan”,“ate”,“nat”,“bat”] Output: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]

Example 2:

Input: strs = [“”] Output: [[“”]]

Example 3:

Input: strs = [“a”] Output: [[“a”]]

Constraints:

• 1 <= strs.length <= 104
• 0 <= strs[i].length <= 100
• strs[i] consists of lowercase English letters.

解题思路

朴素解法

字符串是一个字符组成的数组（可忽略最后的间隔符'\0'），每个字符的ASCII码其实就是数字，是可以排序的，那么字母异位词排序后肯定是相同的，可以用这个值做key，然后把对应的字符串加到后面的列表中。最后循环这个字典，组合最终结果列表即可。

我的答案

朴素解法答案

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        anagrams_dict: Dict[str, List[str]] = {}
        for s in strs:
            sorted_s = ''.join(sorted(s))
            if not anagrams_dict.get(sorted_s):
                anagrams_dict[sorted_s] = [s]
            else:
                anagrams_dict[sorted_s].append(s)
        
        answer: List[List[str]] = []
        for _, v in anagrams_dict.items():
            answer.append(v)

        return answer

优化答案(语法优化版)

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        anagrams = defaultdict(list)
        for s in strs:
            sorted_s = ''.join(sorted(s))
            anagrams[sorted_s].append(s)
    
        return list(anagrams.values())