0049. 字母异位词分组 · ttttt

# 0049. 字母异位词分组 ## 题目地址(49. 字母异位词分组) <https://leetcode-cn.com/problems/group-anagrams/> ## 题目描述 ``` <pre class="calibre18">``` 给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。示例: 输入: ["eat", "tea", "tan", "ate", "nat", "bat"] 输出: [ ["ate","eat","tea"], ["nat","tan"], ["bat"] ] 说明：所有输入均为小写字母。不考虑答案输出的顺序。 ``` ``` ## 前置知识 - 哈希表 - 排序 ## 公司 - 阿里 - 腾讯 - 百度 - 字节 ## 思路一个简单的解法就是遍历数组，然后对每一项都进行排序，然后将其添加到 hashTable 中，最后输出 hashTable 中保存的值即可。这种做法空间复杂度 O(n)，假设排序算法用的快排，那么时间复杂度为 O(n \* klogk), n 为数组长度，k 为字符串的平均长度代码： ``` <pre class="calibre18">``` var groupAnagrams = function (strs) { const hashTable = {}; function sort(str) { return str.split("").sort().join(""); } // 这个方法需要排序，因此不是很优，但是很直观，容易想到 for (let i = 0; i < strs.length; i++) { const str = strs[i]; const key = sort(str); if (!hashTable[key]) { hashTable[key] = [str]; } else { hashTable[key].push(str); } } return Object.values(hashTable); }; ``` ``` 下面我们介绍另外一种方法，我们建立一个 26 长度的 counts 数组（如果区分大小写，我们可以建立 52 个，如果支持其他字符依次类推）。然后我们给每一个字符一个固定的数组下标，然后我们只需要更新每个字符出现的次数。最后形成的 counts 数组如果一致，则说明他们可以通过交换顺序得到。这种算法空间复杂度 O(n), 时间复杂度 O(n \* k), n 为数组长度，k 为字符串的平均长度. ![](https://img.kancloud.cn/51/59/5159fecf7b59a60336c762dede9225c8_830x328.jpg) ## 关键点解析 - 桶排序 ## 代码 - 语言支持: Javascript，Python3 ``` <pre class="calibre18">``` /* * @lc app=leetcode id=49 lang=javascript * * [49] Group Anagrams */ /** * @param {string[]} strs * @return {string[][]} */ var groupAnagrams = function (strs) { // 类似桶排序 let counts = []; const hashTable = {}; for (let i = 0; i < strs.length; i++) { const str = strs[i]; counts = Array(26).fill(0); for (let j = 0; j < str.length; j++) { counts[str[j].charCodeAt(0) - "a".charCodeAt(0)]++; } const key = counts.join(""); if (!hashTable[key]) { hashTable[key] = [str]; } else { hashTable[key].push(str); } } return Object.values(hashTable); }; ``` ``` Python3 Code: ``` <pre class="calibre18">``` class Solution: def groupAnagrams(self, strs: List[str]) -> List[List[str]]: """ 思路同上，在Python中，这里涉及到3个知识点： 1. 使用内置的 defaultdict 字典设置默认值； 2. 内置的 ord 函数，计算ASCII值（等于chr）或Unicode值(等于unichr)； 3. 列表不可哈希，不能作为字典的键，因此这里转为元组； """ str_dict = collections.defaultdict(list) for s in strs: s_key = [0] * 26 for c in s: s_key[ord(c)-ord('a')] += 1 str_dict[tuple(s_key)].append(s) return str_dict.values() ``` ``` **复杂度分析** 其中 N 为 strs 的长度， M 为 strs 中字符串的平均长度。 - 时间复杂度：O(N∗M)O(N \* M)O(N∗M) - 空间复杂度：O(N∗M)O(N \* M)O(N∗M) 大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：<https://github.com/azl397985856/leetcode> 。目前已经 37K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg)