作者: Eswai (eswai@Foxmail.com) CSDN: blog.csdn.net/eswai
Given an array of strings, group anagrams together.
Example:, Given:
[“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
Return:
[ [“ate”, “eat”,”tea”], [“nat”,”tan”], [“bat”] ]
Note: All inputs will be in lower-case.
Anagrams即字母顺序颠倒的字符串，例如”abc”,”acb”和”bca”是anagrams，”abc”和”acd”就不是。 传送门：49. Group Anagrams 相关题目：242. Valid Anagrams和 438. Find All Anagrams in a String
两级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; }};新闻热点
疑难解答
