0049. 字母异位词分组
题目地址(49. 字母异位词分组)
https://leetcode-cn.com/problems/group-anagrams/
题目描述
给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。示例:输入: ["eat", "tea", "tan", "ate", "nat", "bat"]输出:[ ["ate","eat","tea"], ["nat","tan"], ["bat"]]说明：所有输入均为小写字母。不考虑答案输出的顺序。前置知识
哈希表
排序
公司
阿里
腾讯
百度
字节
思路
一个简单的解法就是遍历数组，然后对每一项都进行排序，然后将其添加到 hashTable 中，最后输出 hashTable 中保存的值即可。
这种做法空间复杂度 O(n)， 假设排序算法用的快排，那么时间复杂度为 O(n * klogk), n 为数组长度，k 为字符串的平均长度
代码：
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 为字符串的平均长度.
实际上，这就是桶排序的基本思想。 很多题目都用到了这种思想， 读者可以留心一下。
关键点解析
桶排序
代码
语言支持: Javascript，Python3, CPP
JS Code:
/* * @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:
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 list(str_dict.values())CPP Code:
class Solution {public: vector<vector<string>> groupAnagrams(vector<string>& A) { unordered_map<string, int> m; vector<vector<string>> ans; for (auto &s : A) { auto p = s; sort(p.begin(), p.end()); if (!m.count(p)) { m[p] = ans.size(); ans.push_back({}); } ans[m[p]].push_back(s); } return ans; }};复杂度分析
其中 N 为 strs 的长度， M 为 strs 中字符串的平均长度。
时间复杂度：$O(N * M)$
空间复杂度：$O(N * M)$
大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
最后更新于
这有帮助吗？