49. Group Anagrams

https://leetcode.com/problems/group-anagrams/

solution

• hash的key有要求，本题采用sort后的字符串作为key

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        query = {}
        for string in strs:
            string_counter = "".join(sorted(string))  # 注意对字符串sort之后会变成 字符list
            if string_counter in query:
                query[string_counter].append(string)
            else:
                query[string_counter] = [string]
        return [i[1] for i in query.items()]

时间复杂度：O(nklog(k)), where n=|strs|, k=|strs[i]| 空间复杂度：O(nk)

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

follow up

*249. Group Shifted Strings

class Solution:
    def groupStrings(self, strings):
        normalized_to_group = collections.defaultdict(list)
        for s in strings:
            normalized_chars = []
            shift = ord(s[0]) - ord('a')
            for char in s:
                normalized_char_code = ord(char) - shift
                if normalized_char_code < ord('a'):
                    normalized_char_code += 26
                normalized_chars.append(chr(normalized_char_code))

            normalized_string = ''.join(normalized_chars)
            normalized_to_group[normalized_string].append(s)
        return list(normalized_to_group.values())

时间复杂度：O(nk) 空间复杂度：O(n)

242. Valid Anagram