C++ solution using hashmap and 2-bit codec


  • 1
    R
    class Solution {
    public:
        vector<string> findRepeatedDnaSequences(string s) {
            unordered_map<char, int> dict;
            dict['A'] = 0; dict['C'] = 1; dict['G'] = 2; dict['T'] = 3;
            
            unordered_map<int, int> words;
            vector<string> res;
            int t=0, i;
            for(i=0; i<9; i++)
                t = t<<2 | dict[s[i]];
            
            for(;i<s.size(); ++i) {
                t = t<<2 & 0xFFFFF | dict[s[i]];
                if(words[t]++ == 1)
                    res.push_back(s.substr(i-9, 10));
            }
            return res;
        }
    };
    

Log in to reply
 

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