49. Group Anagrams

[fockspaces]

If the both strings are the same in the sorted char order, they are anagram each other. So we can sorted each elements in strs first, and then store each original strs by its ordered str as a key.

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        ordered_strs = ([''.join(sorted(s)) for s in strs])
        str_dict = {}
        for i, ordered_str in enumerate(ordered_strs):
            if ordered_str not in str_dict:
                str_dict[ordered_str] = []
            str_dict[ordered_str].append(strs[i])
        return str_dict.values()

[fockspaces]

1. instead of ordered each element, we can just create a mapping for counting each characters.
2. since the dict cannot hash a list into key, we can make the list into tuple type
3. we can avoid the "not in set" case by initialize the default dict

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        str_dict = defaultdict(list)
        for s in strs:
            mapping = [0] * 26
            for c in s:
                mapping[ord(c) - ord('a')] += 1
            str_dict[tuple(mapping)].append(s)
        return str_dict.values()