LeetCode Anagrams - JAVA - 编程开发网

Anagrams

Given an array of strings, return all groups of strings that are anagrams.

Note: All inputs will be in lower-case.

本题最巧妙的思想：

因为所谓的anagram是字符位置不一样，字符串是一样的，那么就把该字符排序之后作为map的关键字。

排序之后作为关键字-绝！

vector
  
    anagrams(vector
   
     &strs) { vector
    
      vst; if (strs.size() < 2) return vst; map
     
       > msvs; for (int i = 0; i < strs.size(); i++) { string s = strs[i]; sort(s.begin(), s.end());//精华，最巧妙的地方：排序后作为map的关键字。黄绢幼妇外孙！ msvs[s].push_back(strs[i]); } for (auto it:msvs) { if (it.second.size() > 1) vst.insert(vst.end(),it.second.begin(), it.second.end()); } return vst; }

下面也是hash思想写的程序，程序应该正确了，可惜超时。还是需要像上面那样进一步优化。

vector
  
    anagrams(vector
   
     &strs) { vector
    
      vst; if (strs.size() < 2) return vst; vector
     
       v1, v2; int n = strs.size(); for (int i = 0; i < n; i++) { bool flag = false; vst.push_back(strs[i]); v1.clear(); v1.resize(26,0); for (int k = 0; k < strs[i].length(); k++) { v1[strs[i][k]-'a']++; } for (int j = i+1; j < n; j++) { if (strs[i] == strs[j]) continue; v2.clear(); v2.resize(26,0); for (int k = 0; k < strs[j].length(); k++) { v2[strs[j][k]-'a']++; } if (v1 == v2) { vst.push_back(strs[j]); strs.erase(strs.begin()+j); n--; flag = true; } } if (!flag) vst.pop_back(); } return vst; }