【LeetCode】字母异位词分组（python）

题目描述

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

示例:

输入: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”],
输出:
[
[“ate”,“eat”,“tea”],
[“nat”,“tan”],
[“bat”]
]
说明：
所有输入均为小写字母。
不考虑答案输出的顺序。

解题思路

将词进行排序，并使用字典存储，其中键存储排序后的字符串，值为字符串数组，存储排序前的字符串。

		d = {}
        for ele in strs:
            s = ''.join(sorted(ele))
            if s not in d.keys():
                d[s] = [ele]
            else:
                d[s].append(ele)

完整代码

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        # 超出时间限制
        # result = []
        # for ele in strs:
        #     if len(result) ==0:
        #         result.append([ele])
        #     else:
        #         entry = False
        #         for e in result:
        #             if sorted(e[0]) == sorted(ele):
        #                 e.append(ele)
        #                 entry = True
        #         if not entry:
        #             result.append([ele])
        # return result
        
        # 字典法
        d = {}
        for ele in strs:
            s = ''.join(sorted(ele))
            if s not in d.keys():
                d[s] = [ele]
            else:
                d[s].append(ele)
        result = []
        for k in d.keys():
            result.append(d[k])
        return result