Given an array of strings, group anagrams together.
Example:,
Given:
Return:
[
[“ate”, “eat”,“tea”],
[“nat”,“tan”],
[“bat”]
]
Note: All inputs will be in lower-case.
Anagrams即字母顺序颠倒的字符串,例如"abc","acb"和"bca"是anagrams,"abc"和"acd"就不是。
传送门:
相关题目:和
两级map结构,对每一个字符串用低级map来统计每个字母出现的个数,在到高级map中查询是否出现过同一anagram的字符串,如果有则插入到输出向量的指定位置,没有则插入到输出向量的尾部。
本方法的特点在于用string类型替代了数组来统计每个字母出现的个数。
运行时间29ms,超过93.45%
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
vector<vector<string>> result;
//输入空则输出空
if(strs.empty()) return result;
//不能用<vector<int>,int>,因为vector<int>不能用<符号来比较
unordered_map<string,int> map;
int count = 0;
for(string str:strs){
string m(26,0);//string可以看成是一个数组
for(char ch:str){
m[ch-'a']++;
}
if(map.find(m) == map.end()){
//map中没找到则将字符串str插入result尾部,更新map,count
map.insert(pair<string,int>(m,count));
count++;
vector<string> rs;
rs.push_back(str);
result.push_back(rs);
}
else{
//字符串str的anagram已经出现过,则将str插入result相应位置
result[map[m]].push_back(str);
}
}
return result;
}
};
因篇幅问题不能全部显示,请点此查看更多更全内容
Copyright © 2019- haog.cn 版权所有 赣ICP备2024042798号-2
违法及侵权请联系:TEL:199 1889 7713 E-MAIL:2724546146@qq.com
本站由北京市万商天勤律师事务所王兴未律师提供法律服务