python3实现字母异位词分组——哈希表(Hash Table)

题目

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

示例:

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

说明：

所有输入均为小写字母。
不考虑答案输出的顺序。

题目来源

提示：

leetcode倒数第二个测试用例给的数组非常大，用普通的方法多半会超时（飙泪），必须使用奇淫技巧来突破。有两个切入点：

1. 当且仅当两个字符串的排序字符串相等时，它们是字母异位词。

   "tea" ->"aet"；“eat"->"aet"

   "poor"->"oopr"；”ropo“->"oopr"

   "and"->"adn"

   "ad"->"ad"

2. 当且仅当它们的字符计数（每个字符的出现次数）相同时，两个字符串是字母异位词。

思路

按照第一个思路，并且利用哈希表减少运算时间。

python中使用”字典“维护一个分组表，键值（key）为排序后的字符串，值（value）为子分组的下标

result=[
["ate","eat","tea"],
["nat","tan"],
["bat"]]

group={"aet":0,"ant":1"abt":2}

每次对字符串排序后加入对应的分组中，或者创建新的分组

python3实现

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        result=[]
        # key为排序后单词，value为result的分组下标
        group={}
        for i in range(len(strs)):
            temp_list=list(strs[i])
            temp_list.sort()
            sorted_string="".join(temp_list)
            if sorted_string in group:
                result[group[sorted_string]].append(strs[i])
            else:
                group[sorted_string]=len(group)
                result.append([strs[i]])
        return result

做题心得

如果15分钟想不出来特别妙的方法就直接看答案吧...毕竟就算思路对了实现也要大半天...

python3实现字母异位词分组——哈希表(Hash Table)

原文：https://www.cnblogs.com/zhoujiayingvana/p/12339775.html