2013.12.15 22:00
Given an array of strings, return all groups of strings that are anagrams.
Note: All inputs will be in lower-case.
Solution:
Anagrams means that strings composed of the same group of letters, such as [ate, eat, tea]. They'll become the same when sorted: aet.
My solution is to sort every string, and sort the array according to the sorted form of each string element. Then group the strings together by anagrams.
Time compexity is O(n * log(n)), where n is the length of the array. Space complexity is O(n).
Accepted code:
1 // 1CE, 1AC 2 #include3 #include 4 #include 5 using namespace std; 6 7 typedef struct st{ 8 public: 9 string str;10 string sorted_str;11 12 st(string _str = "", string _sorted_str = "") {13 str = _str;14 sorted_str = _sorted_str;15 }16 }st;17 18 bool comparator(const st &x, const st &y)19 {20 // 1CE here, return a.sorted_str < b.sorted_str;21 return x.sorted_str < y.sorted_str;22 }23 24 class Solution {25 public:26 vector anagrams(vector &strs) {27 // IMPORTANT: Please reset any member data you declared, as28 // the same Solution instance will be reused for each test case.29 int max_len = 0;30 int i, j, n;31 char *ps = nullptr;32 33 result.clear();34 v.clear();35 36 n = strs.size();37 if(n <= 0){38 return result;39 }40 for(i = 0; i < n; ++i){41 if(strs[i].length() > max_len){42 max_len = strs[i].length();43 }44 }45 ps = new char[max_len + 1];46 47 string s, ss;48 for(i = 0; i < n; ++i){49 s = strs[i];50 strcpy(ps, s.data());51 sort(ps, ps + s.length());52 ss = string(ps);53 v.push_back(st(s, ss));54 }55 sort(v.begin(), v.end(), comparator);56 delete[] ps;57 i = 0;58 while(i < n){59 j = i;60 while(j < n && v[i].sorted_str == v[j].sorted_str){61 ++j;62 }63 if(j - i > 1){64 while(i < j){65 result.push_back(v[i].str);66 ++i;67 }68 }69 i = j;70 }71 v.clear();72 73 return result;74 }75 private:76 vector v;77 vector result;78 };