My short and simple hash solution!


  • 0
    P
    unsigned int hashF(string s) {
        unsigned int hash = 131;
        for (auto c: s)
            hash = hash * c * c + c;
        return (hash & 0x7FFFFFFF);
    }
    
    vector<int> findSubstring(string s, vector<string> words) {
        unsigned int wordsHash = 0;
        for (auto word: words)
            wordsHash += hashF(word);
        vector<int> ans;
        int wlen = words[0].size(), wcnt = words.size(), slen = s.size();
        for (unsigned int offset = 0, sHash = 0;offset < wlen;++offset)
            for (int i = offset;i < slen;i += wlen) {
                sHash += hashF(s.substr(i,wlen));
                if (i-offset >= wlen*wcnt)
                    sHash -= hashF(s.substr(i-wlen*wcnt,wlen));
                if (sHash == wordsHash)
                    ans.push_back(i-wlen*wcnt+wlen);
            }
        return ans;
    }

  • 0
    Y

    could you explain what does "if (i-offset >= wlenwcnt) sHash -= hashF(s.substr(i-wlenwcnt,wlen));" mean


Log in to reply
 

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