g***j 发帖数: 1275 | 1 Given an array of strings, return all groups of strings that are anagrams.
Note: All inputs will be in lower-case.
上面大小测试集都过了,但是总感觉有问题,至少感觉很臃肿,请问我写的这个代码哪
可以改进一下?
int getHashcode(string s) {
int code = 2166136261U;
sort(s.begin(), s.end());
for(int i = 0 ; i < s.length(); i++) {
code = code ^ (s[i]);
code = code * 16777619;
}
return code;
}
class Solution {
public:
vector anagrams(vector &strs) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector results;
if(strs.size() <= 1) return results;
map myMap;
map myCode;
for(int i = 0; i < strs.size(); i++) {
myCode[strs[i]] = getHashcode(strs[i]);
}
for(int i = 0; i < strs.size(); i++) {
myMap[myCode[strs[i]]] = 0;
}
for(int i = 0; i < strs.size(); i++) {
myMap[myCode[strs[i]]]++;
}
for(int i = 0; i < strs.size(); i++) {
if(myMap[myCode[strs[i]]] > 1 ) {
results.push_back(strs[i]);
}
}
return results;
}
}; |
r*****s 发帖数: 74 | 2 code = code ^ (s[i]);
code = code * 16777619;
=>
code ^= s[i];
code *= 16777619;
能省几个字符…… |
g***j 发帖数: 1275 | 3 what about the body? I used four loops, any way to reduce some?
and also I used two maps, is one enough?
【在 r*****s 的大作中提到】 : code = code ^ (s[i]); : code = code * 16777619; : => : code ^= s[i]; : code *= 16777619; : 能省几个字符……
|
r**h 发帖数: 1288 | 4 用一个multimap
左边是一个string,右边是对应的字符串的index
因为所有anagram,他们sort后的字符串都是一样的。
第一轮loop,sort每个string,按照sort的结果加入到multimap里
第二轮遍历multimap,输出字符串
multimap mmp;
multimap::iterator it;
vector results;
string tmp;
for(int i=0; i
tmp = strs[i];
sort(tmp.begin(), tmp.end());
mmp.insert(std::pair(tmp, i));
}
for(it=mmp.begin(); it!=mmp.end(); it++){
results.push_back(strs[(*it).second]);
}
return results; |