A single loop solution that avoid assignment operation more than twice

  • 0

    Guys, we can play with the trick.
    Since some sub-string may appear more than twice, I just storage the answer immediately and use an "hash_map<string,bool>" structure to avoid triple lookup.
    See the following code in C++.

    class Solution {
        vector<string> findRepeatedDnaSequences(string s) {
            vector<string> ans;
            if( s.size() < 11 ) return ans;
            unordered_map<string,bool> collection;
            for( int i=0 ; i<s.size()-9 ; i++){
                auto sub = s.substr(i,10);
                auto finder = collection.find(sub);
                if( finder != collection.end() ){
                    if( finder->second ) ans.push_back(sub);
                    finder->second = false;
                } else collection[sub] = true;
            return ans;

Log in to reply

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