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: }
No comments:
Post a Comment