C++ useing trie


  • 0
    S
    class Solution {
    public:
        int buf[1024*1024];
        int cur_button;
        vector<string> result;
        
        int get_int(char tag){
            switch (tag){
                case 'A': return 0;
                case 'C': return 1;
                case 'G': return 2;
                case 'T': return 3;
                default : return -1;
            }
        }
        
        char get_char(int tag){
            switch (tag){
                case 0: return 'A';
                case 1: return 'C';
                case 2: return 'G';
                case 3: return 'T';
                default : return '\0';
            }
        }
        
        void insert(int array[], int offset){
            int cur = 0;
            for(int i=0; i<10; ++i){
                if(buf[cur+array[(i+offset)%10]] == 0){
                    buf[cur+array[(i+offset)%10]] = cur_button;
                    cur_button +=4;
                }
                cur = buf[cur+array[(i+offset)%10]];
            }
            if(++buf[cur] == 2){
                string ret;
                for(int i=0; i<10; ++i){
                    ret += get_char(array[(i+offset)%10]);
                }
                result.push_back(ret);
            }
        }
        
        vector<string> findRepeatedDnaSequences(string s) {
            memset(buf, 0, sizeof(buf));
            cur_button = 4;
            result.clear();
            if(s.size() < 10) return result;
            int array[10];
            for(int i=0; i<9; ++i){
                array[i] = get_int(s[i]);
            }
            int off_set = 0;
            for(int i=9; i<s.size(); ++i){
                array[i%10] = get_int(s[i]);
                insert(array, off_set);
                off_set = (off_set+1)%10;
            }
            return result;
        }
    };

Log in to reply
 

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