LeetCode 热题 100_2-字母异位词分组

✨✨ 欢迎大家来到小伞的大讲堂✨✨养成好习惯先赞后看哦~所属专栏Leetcode热门100小伞的主页xiaosan_bloggitee:许星让 (xu-xingrang) - Gitee.com制作不易点个赞吧谢谢喵0.题目49. 字母异位词分组 - 力扣LeetCode1.排序由于互为字母异位词的两个字符串包含的字母相同因此对两个字符串分别进行排序之后得到的字符串一定是相同的故可以将排序之后的字符串作为哈希表的键。我们不改变原始元素借用临时变量str进行排序比较将原始数据放入哈希表中vectorvectorstring groupAnagrams(vectorstring strs) { //字母异位词排序的结果相同 unordered_mapstring, vectorstring hash; for (string str : strs) { string key str;//使用临时变量 sort(key.begin(), key.end()); hash[key].push_back(str);//记录原始数据 } vectorvectorstring ret; for (auto it hash.begin(); it ! hash.end(); it) { ret.push_back(it-second); } return ret; }复杂度分析时间复杂度O(nklogk)其中 n 是 strs 中的字符串的数量k 是 strs 中的字符串的的最大长度。需要遍历 n 个字符串对于每个字符串需要 O(klogk) 的时间进行排序以及 O(1) 的时间更新哈希表因此总时间复杂度是 O(nklogk)。空间复杂度O(nk)其中 n 是 strs 中的字符串的数量k 是 strs 中的字符串的的最大长度。需要用哈希表存储全部字符串。