A Method Using Quick Sort


  • 0
    B
    class Solution {
    public:
    
        struct node{
            int piece;
            int idx;
            node(int p, int i):piece(p), idx(i){}
            friend bool operator<(const node &A, const node &B){
                return A.piece < B.piece;
            }
        };
    
        vector<string> findRepeatedDnaSequences(string s) {
            int mask = (1<<20) - 1;
            int L = s.length(), piece;
            vector<node> buf;
            vector<string> ans;
            if(L < 10)return ans;
            
            piece = 0;
            for(int i = 0; i < 10; i ++){
                piece <<= 2;
                switch(s[i]){
                    case 'A':
                    break;
                    case 'C':
                    piece |= 1;
                    break;
                    case 'G':
                    piece |=2;
                    break;
                    default:
                    piece |= 3;
                }
            }
            buf.push_back(node(piece,0));
            for(int i = 10; i < L; i ++){
                piece <<= 2;
                piece &= mask;
                switch(s[i]){
                    case 'A':
                    break;
                    case 'C':
                    piece |= 1;
                    break;
                    case 'G':
                    piece |=2;
                    break;
                    default:
                    piece |= 3;
                }
                buf.push_back(node(piece,i-9));
            }
            
            sort(buf.begin(),buf.end());
            
            for(int i = 0; i < buf.size() - 1;){
                if(buf[i].piece == buf[i+1].piece){
                    ans.push_back(s.substr(buf[i].idx,10));
                    i ++;
                }
                else i ++;
                while(i < buf.size() && buf[i].piece == buf[i-1].piece)i++;
            }
            
            return ans;
        }
    };

Log in to reply
 

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