10 lines C++ code, 8 ms passed!


  • 34
    P
    vector<string> findRepeatedDnaSequences(string s) {
        char  hashMap[1048576] = {0};
        vector<string> ans;
        int len = s.size(),hashNum = 0;
        if (len < 11) return ans;
        for (int i = 0;i < 9;++i)
            hashNum = hashNum << 2 | (s[i] - 'A' + 1) % 5;
        for (int i = 9;i < len;++i)
            if (hashMap[hashNum = (hashNum << 2 | (s[i] - 'A' + 1) % 5) & 0xfffff]++ == 1)
                ans.push_back(s.substr(i-9,10));
        return ans;
    }

  • 0
    U

    Your solution is pretty cool!!!


  • 0
    K

    Amazing. Now I get it!


  • 14
    A

    It is very dangerous using char for counting.

    Your code will have the wrong answer for the a test case appear more than 256 times such as

    "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
    

    a simple solution is only allowing hashMap to has three status, 0 for none, 1 for 1, 3 for multiple.

    vector<string> findRepeatedDnaSequences(string s) {
        char flag[262144] ={0};
        vector<string> result;
        int len,DNA=0,i;
        if((len=s.length())< 11) return result;
        for(i = 0 ; i < 9; i++)
            DNA = DNA << 2| (s[i] - 'A' + 1) % 5;
        for(i = 9;i<len;i++)
        {
            DNA = (DNA<<2 & 0xFFFFF)|(s[i] - 'A' + 1)%5;
                if(!(flag[DNA>>2]&(1<<((DNA&3) << 1)))) 
                    flag[DNA>>2] |= (1<<((DNA&3) << 1));
                else if(!(flag[DNA>>2]&(2<<((DNA&3) << 1)))) 
                {
                    result.push_back(s.substr(i-9,10));
                    flag[DNA>>2] |= (2<<((DNA&3) << 1));
                }
        }
        return result;
    }

  • 0
    P

    yes! I know it. I just want to make the code short and cool. Your solution is right! Thank you!


  • 0
    A

    Amazing Solution!


  • 0

    what 1048576 means ???


  • 2
    P

    It's 4^10, the number of all possible different sequences with 10 DNA.


Log in to reply
 

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