Solved this problem by using hashes. AC. C++


  • 0
    D

    For each substring let's find the hash and then check whether this hash already had been found.
    If this hash was found only once we can push this substring to our result but then we should to mark this substring as used, we can do this by marking it's hash.

    class Solution {
        long long findHashNumber(string  s) {
            long long res = s[0];
            long long p = 5;
            for (int i = 1; i < s.size(); i++) {
                res += s[i] * p;
                p *= 5;
            }
            return res;
        }
    public:
    
        vector<string> findRepeatedDnaSequences(string s) {
            set<long long> setOfHashes;
            set<long long> usedHashes;
            vector <string> result;
            if (s.size() < 10) return result;
            for (int i = 0; i < s.size() - 9; i++) {
                long long hash = findHashNumber(s.substr(i, 10));
                if (usedHashes.count(hash)) continue;
                if (setOfHashes.count(hash)) {
                    result.push_back(s.substr(i, 10));
                    usedHashes.insert(hash);
                }
                else
                    setOfHashes.insert(hash);
            }
            return result;
        }
    };

  • 0
    H
    This post is deleted!

Log in to reply
 

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