A solution that really runs in O(n)


  • -1
    M

    I've seen some discussions claiming they are O(n) while they are not.
    It is expensive to compare two whole vectors every time.
    This is my solution, that does run in O(n).
    If you feel panaroic, you can check if each match is truly a match,
    though it is kind of unnecessary IMO.

    class Solution {
    public:
        vector<int> findAnagrams(string s, string p) {
            vector<int> result;
            int N = s.size();
            int P = p.size();
            if (N < P) return result;
            
            // Initial rand values
            vector<unsigned> rand_val(26);
            for (int i = 0; i < 26; i++) rand_val[i] = rand();
            
            // Target for matching
            unsigned target = 0;
            for (char c : p) target += rand_val[c - 'a'];
            
            // sum[i] : sum of hash for s[0], s[1], ..., s[i]
            vector<unsigned> sum(N);
            sum[0] = rand_val[s[0] - 'a'];
            for (int i = 1; i < N; i++) sum[i] = sum[i - 1] + rand_val[s[i] - 'a'];
            
            // Check all possible hash sums
            for (int i = P; i <= N; i++) {
                unsigned diff = sum[i - 1];
                if (i != P) diff -= sum[i - P - 1];
                
                if (diff == target) {
                    // If you feel panaroic you can explicitly check the string,
                    // in case of hash collision
                    result.push_back(i - P);
                }
            }
            return result;
        }
    };
    

Log in to reply
 

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