作者: 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 相關(guān)題目：242. Valid Anagrams和 438. Find All Anagrams in a String
兩級map結(jié)構(gòu)，對每一個字符串用低級map來統(tǒng)計每個字母出現(xiàn)的個數(shù)，在到高級map中查詢是否出現(xiàn)過同一anagram的字符串，如果有則插入到輸出向量的指定位置，沒有則插入到輸出向量的尾部。 本方法的特點(diǎn)在于用string類型替代了數(shù)組來統(tǒng)計每個字母出現(xiàn)的個數(shù)。
運(yùn)行時間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可以看成是一個數(shù)組 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已經(jīng)出現(xiàn)過，則將str插入result相應(yīng)位置 result[map[m]].push_back(str); } } return result; }};新聞熱點(diǎn)
疑難解答
