# Use unordered set to solve this question(C++)

• Here I show the thinking process to solve this question.
And another two method can not be accepted by the OJ .

``````//事实证明，还是可以用哈希表，直接建立一个string的哈希表太大了！
//因为string的每一位都只有四种可能，我用一个int位来代替一个10位的string，ACGT分别代表两位00 01 10 11，即
//用一个20位的int值表示10位的string
//再用hash来建立int的表进行查找～即可
vector<string> findRepeatedDnaSequences(string s) {
vector<string> res;
int i,foo_i;
string foo,bar;
unordered_set<int> A;
int size=s.length();
if(size<=10)
return res;
for(i=0;i+10<=size;i++){
foo=s.substr(i,10);
foo_i=str2num(foo);
if(A.find(foo_i)==A.end()){
A.insert(foo_i);
}
else{
if(find(res.begin(),res.end(),foo)==res.end())
res.push_back(foo);
}
}
return res;
}
int str2num(string A){
int i,res=0;
for(i=0;i<10;i++){
if(A[i]=='A')
res+=0;
else if(A[i]=='C')
res+=1;
else if(A[i]=='T')
res+=2;
else if(A[i]=='G')
res+=3;
res=res<<2;
}
return res;
}
//Time Limit method
/*
vector<string> findRepeatedDnaSequences(string s) {
vector<string> res;
int i,loc;
string foo,bar;
int size=s.length();
if(size<=10)
return res;
for(i=0;i+10<=size;i++){
foo=s.substr(i,10);
if(find(res.begin(),res.end(),foo)!=res.end())
continue;
loc=s.find(foo,i+1);
if(loc>0){
res.push_back(foo);
for(;s[i+10]==s[loc+10]&&i+10<=size&&loc+10<=size;i++,loc++){
if(find(res.begin(),res.end(),foo)!=res.end())
res.push_back(s.substr(i+1,10));
}
}
}
return res;
}
*/
//建立一个哈希表，结构出现 Memory Limit Exceeded的错误
/*
vector<string> findRepeatedDnaSequences(string s) {
vector<string> res;
int i;
string foo,bar;
unordered_set<string> A;
int size=s.length();
if(size<=10)
return res;
for(i=0;i+10<=size;i++){
foo=s.substr(i,10);

if(A.find(foo)==A.end()){
A.insert(foo);
}
else{
res.push_back(foo);
}
}
sort(res.begin(),res.end());
res.erase(unique(res.begin(),res.end()),res.end());
return res;
}
*/``````

• why is left shift 2bit,not1bit?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.