LeetCode [热题100]（49.字母异位词分组）

常规
1

49. 字母异位词分组

前言

字母异位词：两个字符串互为字母异位词，当且仅当两个字符串包含的字母相同。
比如[“hello”, “lloeh”, “olehl”]，都具有h、e、o和两个l，只是字母顺序不同
思路：同一组字母异位词具有相同的标志，比如排序后相同。因此可以将排序后的字符串作为哈希表的键，字母异位词列表作为哈希表的值，这样同一组字母异位词就在同一个列表中
流程：遍历每个字符串，对于每个字符串，得到该字符串所在的一组字母异位词的标志（即排序后的字符串），将当前字符串加入该组字母异位词的列表中。遍历全部字符串之后，哈希表中的每个键值对即为一组字母异位词。

代码（C++）

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        // 字母异位词排序后的结果是唯一的，可以以此做哈希表的key
        vector<vector<string>>res; // 结果集
        unordered_map<string,vector<string>>mp; // 字母异位词分组列表
	
        // 遍历字符串
        for(auto&str:strs){
            string key=str;
            sort(key.begin(),key.end()); // 排序字符串以获取字母异位词标志
            mp[key].push_back(str);
        }
	
        // 将分组结果加入结果集
        for(auto&pair:mp){
            res.push_back(pair.second);
        }

        return res;
    }
};
1 个赞