Can anyone tell me how get AC result below 50ms using C++


  • 0
    C

    I tested several AC codes posted by others, finding that using bit
    manipulation (C++), we can only get AC result in more than 100ms, can
    anyone post solutions below 50ms?


  • 0
    O

    I'm interested in this too - of course could cheat and do lookup table (only 30 cases, so shouldn't take long), but I assume there is a legit solutions.

    Here is my solution so far - 108ms. I hoped bitwise operations would be able to get time down, but didn't seem to do too much better

    vector<string> findRepeatedDnaSequences(string s) {
        int mask = ~0, i, id=0;
        mask<<=20;
        mask = ~mask;
        int n = s.length();
        vector<string> out;
        unordered_set<int> seen, included;
        i=-1;
        while(++i<n){
            id<<=2;
            id&=mask;
            if (s[i]=='G') id ^=1;
            if (s[i]=='C') id ^=2;
            if (s[i]=='T') id ^=3;
            if (i<9) continue;
            if (seen.find(id)==seen.end()) {seen.insert(id); continue;}
            if (included.find(id)!=included.end()) continue;
            included.insert(id);
            out.push_back(s.substr(i-9, 10));
        }
        return out;
    }

  • 2
    J

    You need to use array instead of STL to get the best performance.

    The following code runs in 18ms, it's slightly modified from my other question.

    vector<string> findRepeatedDnaSequences(string &s) {
        vector<string> r;
        int t = 0, i = 0, ss = s.size(), m[1 << 20] = {0};
        while (i < 9)
            t = t << 2 | s[i++] >> 1 & 3;
        while (i < ss)
            if (m[t = t << 2 & 0xFFFFF | s[i++] >> 1 & 3]++ == 1)
                r.emplace_back(s, i - 10, 10);
        return r;
    }
    

Log in to reply
 

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