Just 7 lines of code!


  • 20
    D

    I am too lazy to design my own hash function; Hence I just used the one provided by C++.

    vector<string> findRepeatedDnaSequences(string s) {
            
            unordered_map<size_t,int> MP;
            hash<string> hash_fn;
            vector<string> ret;
            
            for(int i = 0; i < int(s.size()) - 9; ++i)
                if(MP[hash_fn(s.substr(i,10))]++ == 1 )
                   ret.push_back(s.substr(i,10));
                   
          return ret;
        }

  • 0
    This post is deleted!

  • 0
    I

    nice and neat


  • 0
    S

    Really nice solution. Just have one question. If the two identical substrings overlap (e.g substr(1, 10) and substr(2, 10) ), your code would count them as repeated sequence right? Just from a biology point of view, I personally think that these substrings should not count as repeats.


  • 2
    B

    Is hash<string> guaranteed to return unique keys for unique strings? If not, will your algorithm still work?


  • 0
    D

    In this problem, it is allowed. There is a case that 's' is "AAAAAAAAAAA", and the result is "AAAAAAAAAA"


  • 0
    S

    Oh I see. Thanks a lot!!!


  • 0
    K

    Refer to this question. http://stackoverflow.com/questions/4032209/is-md5-still-good-enough-to-uniquely-identify-files

    theoretically, no hash function could guarantee completely "unique". What a hash function try to guarantee is that "it's extremely hard to find a collision".


  • 0
    C

    Hello, great solution. can you explain MP[hash_fn(s.substr(i,10))]++ == 1. How does it work? Thanks.

    What is wrong with this code below?

    int sz=s.size();

    for(int i=0;i<sz-10;i++)
    {
    string sub=s.substr(i,10);
    size_t hsh=hash_fn(sub);

            unordered_map<size_t,int>::const_iterator got = mp.find (hsh);
            
            if(got == mp.end())
            {
                mp[hsh]=1; //insert an element
            }
            else
            {
                int t=got->second;
                if(t==1) //found
                {
                    ret.push_back(sub);
                    mp[hsh]=2; rewrite
                }
         
            }
        }
        
        return ret;

Log in to reply
 

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