lc187-Repeated DNA Sequences

發表於   |   分類於   |   0 comments   |   
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s) {
        unordered_map<string,int> mp;
        vector<string> result;
        if(s.length()<10) return result;
        
        
        for(int i=0;i<=s.length()-10;i++){
            string temp=s.substr(i,10);
            if(mp.find(temp)==mp.end()) {
                mp[temp]=1;
            }
            else mp[temp]++;
        }
        for(auto k:mp){
            if(k.second>1) result.push_back(k.first);
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution{
public:
vector<string> findRepeatedDnaSequences(string s) {
    int l = s.length();
    // vector<int> set;
    unordered_map<int, int> set;
    unordered_map<int, int> res;
    vector<string> ress_v;
    int k = 0;
    map<int,int> m;
    m['C'-'A'] = 1;
    m['G'-'A'] = 2;
    m['T'-'A'] = 3;
    for (int i = 0; i < l; i+=1) {
        k = k << 2;
        k = k & 0xFFFFF;
        k |= m[s[i]-'A'];
        if (i > 8) {
            if (set[k]>=1 && find(ress_v.begin(), ress_v.end(), s.substr(i-9,10))==ress_v.end())
                ress_v.push_back(s.substr(i-9,10));
            // }
            set[k]+=1;
        }
    }
    // for (auto i:set) {
        // if(set.second > 1)
            // ress_v.pushback{}
    // }
    return ress_v;
}
};