Anagrams
Total Accepted: 12270 Total
Submissions: 52498My Submissions
Given an array of strings, return all groups of strings that are anagrams.
Note: All inputs will be in lower-case.
关键是string的内部字符排序和map容器的迭代
class Solution { public: vector<string> anagrams(vector<string> &strs) { vector<string> res;int n=strs.size(); if(n==0) return res; map<string,vector<int> > ss; char buffer[1000]; for(int i=0;i<n;i++){ strcpy(buffer,strs[i].c_str());//从string拷贝到char* sort(buffer,buffer+strs[i].length());//并排序char* string s=buffer; //再转成string ss[s].push_back(i); } for( map<string,vector<int> >::iterator it=ss.begin();it!=ss.end();it++){//map迭代,*it是pair<?,?> vector<int> &t=it->second; if(t.size()>1){ for(int i=0;i<t.size();i++) res.push_back(strs[t[i]]); } } return res; } };
或者对pair <sorted_string,string> [ ]进行排序,比较pair.first以查重。
class Solution { public: vector<string> anagrams(vector<string> &strs) { vector<pair<string,string> > vec;vector<string> ans; typedef pair<string,string> Pair; int n=strs.size(); if(n==0) return ans; for(int i=0;i<n;i++){ string s=strs[i]; sort(s.begin(),s.end()); vec.push_back(Pair(s,strs[i])); } sort(vec.begin(),vec.end()); string last=vec[0].first;int m=0; for(int i=0;i<=vec.size();i++){ if(i<vec.size()&&vec[i].first==last) m++; else{ if(m>1){ for(int j=i-1;j>=i-m;j--) ans.push_back(vec[j].second); } if(i<vec.size()){ last=vec[i].first,m=1; } } } return ans; } };