刚看到题的想法就是用一个vector存储每个字符串字母与出现次数的哈希映射;哈希映射统计每个字符串中每个字母出现的次数,所有字母出现次数都相等的字符串肯定为异位词分组。类似于vector<unordered_map<char, int>>;但在写的时候发现 在比较的时候,真的写不下去了😂
无奈看了题解,才知道要先将字符串排序再放入哈希表中;键值对为排序后的string和异位的词:unordered_map<string, vetcor<sting>>
这里我用unorded_map<>会比map节省内存;emplace_back()也比push_back()效率高(原因我看了几次都记不住,难受住😭)。还有用引用的话,不占用新的内存,效率也会高一点。😀
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
vector<vector<string>> ans;
map<string, vector<string>> m;
for(const auto& str : strs){
string tmp = str;
sort(tmp.begin(), tmp.end());
m[tmp].emplace_back(str);
}
for(const auto& i : m){ //这里用引用,不开辟新的内存,会节省一些内存;
ans.emplace_back(i.second);
}
return ans;
}
};
看到最大神的解法,就是将每个字母对应成相同顺序排的质数,只要每个字符串的质数之积相等,则必定相同。(不过感觉对于我这阶段的菜鸡超纲了)
难度中等
给定一个字符串数组,将字母异位词组合在一起。字母异位词指字母相同,但排列不同的字符串。
示例:
输入:["eat", "tea", "tan", "ate", "nat", "bat"]输出:[ ["ate","eat","tea"], ["nat","tan"], ["bat"]]
说明:
所有输入均为小写字母。
不考虑答案输出的顺序。