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 {
    public:
        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.