[LeetCode] Anagrams 解题报告

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

Note: All inputs will be in lower-case.

» Solve this problem

[解题思路]
对每一个字符串取水印，然后水印相同的即为anagrams。但是实现上倒是有个问题，最开始取水印的方式如代码中红字所示。但是对于超大字符串，也导致了超时。改为去一个整数hash，但是这种实现的风险是，hash值相同的不见得是anagrams。

目前想不出来好的实现。

[Code]

1:    vector<string> anagrams(vector<string> &strs) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      vector<string> result;  
5:      if(strs.size() ==0) return result;  
6:      map<long, vector<string> > smap;  
7:      for(int i =0; i< strs.size(); i++)  
8:      {  
9:        smap[footprint(strs[i])].push_back(strs[i]);  
10:      }      
11:      for(map<long, vector<string> >::iterator it = smap.begin();  
12:      it!=smap.end(); ++it)  
13:      {  
14:        if(it->second.size() <=1)  
15:          continue;  
16:        result.insert(result.begin(), it->second.begin(), it->second.end());  
17:      }  
18:      return result;  
19:    }  
20:    long footprint(string str)  
21:    {  
22:      int index[26];  
23:      memset(index, 0, 26*sizeof(int));  
24:      for(int i = 0; i < str.size(); i++)   
25:      {   
26:        index[str[i]-'a']++;        
27:      }  
28:      /*string footp;  
29:      for(int i =0; i<26; i++)  
30:      {  
31:        footp.append(1,i+'a');  
32:        stringstream ss;   
33:        ss << index[i];  
34:        footp.append(ss.str());  
35:      }*/  
36:      long footp=0;  
37:      int feed =7;  
38:      for(int i =0; i< 26; i++)  
39:      {  
40:        footp= footp*feed +index[i];  
41:      }  
42:      return footp;   
43:    }