[数据结构与算法]LeetCode 49、字母异位词分组

1、题目：字母异位词分组

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

示例:

输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
输出:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

2、解答

• 排序法：对每个字符串排序，然后具有相同字母的单词排序后得到的字符串是相同的，然后借用字典将这些排序后的字符串作为key，对应的字母异位词作为value。

• 哈希表法：具有相同字母的词，每个字母出现的个数是一样的，所以可以维护一个26位的数组，统计每个单词中字母出现的次数，然后将这个数组转换成可hash的数据结构，当做key，对应value是对应的字母异位词。

    # 排序法
    def groupAnagrams(self, strs):
        """
        使用排序后的单词作为key来保存这整个数组
        :type strs: List[str]  ["eat", "tea", "tan", "ate", "nat", "bat"]
        :rtype: List[List[str]]  [
              ["ate","eat","tea"],
              ["nat","tan"],
              ["bat"]
            ]
        """
        result = {}
        for word in strs:
            sort_word = "".join(sorted(word))
            tmp = result.get(sort_word, [])
            tmp.append(word)
            result[sort_word] = tmp
        return list(result.values())

    def groupAnagrams2(self, strs):
        """
        哈希表法
        :type strs: List[str]  ["eat", "tea", "tan", "ate", "nat", "bat"]
        :rtype: List[List[str]]  [
              ["ate","eat","tea"],
              ["nat","tan"],
              ["bat"]
            ]
        """
        result = {}
        for word in strs:
            chars = [0]*26
            for char in word:
                chars[ord(char)-ord('a')] += 1
            key = tuple(chars)
            tmp = result.get(key, [])
            tmp.append(word)
            result[key] = tmp
        return list(result.values())