Description Link to heading

30.substring-with-concatenation-of-all-words

Solution Link to heading

For each word sequence {s.substr(i, word_len), s.substr(i + word_len, word_len)...} of i($[0, word_len - 1]$), we use sliding window to judge;

We should pay attention to the detail when judging. We can use mp to determine whether substr is in words, and mp_tmp to determine whether it is concatenated substring, if mp is empty, then it is;

For key-value in mp_tmp, if value becomes 0, then erase(key);

Don’t forget dealing with l! It’s also complicated. When mp_tmp becomes empty, mp_tmp[s.substr(l, word_len)]++; l+= word_len;

When the word is in mp but not in mp_tmp, update l and mp_tmp.

Code Link to heading 

class Solution {
  public:
    vector<int> findSubstring(string s, vector<string> &words) {
        unordered_map<string, int> mp;
        int word_len = words[0].size();
        int cnt = 0;
        vector<int> res;
        for (int i = 0; i < words.size(); i++) {
            mp[words[i]]++;
            cnt++;
        }
        if (cnt * word_len > s.size())
            return res;
        // i : [0, word_len - 1], sliding windows for each word sequence
        for (int i = 0; i < word_len; i++) {
            int l = i;
            unordered_map<string, int> mp_tmp = mp;
            // unordered_map<string, int> mp_tmp2 = mp;
            for (int r = i; r <= s.size() - word_len; r += word_len) {
                string tmp = s.substr(r, word_len);
                if (mp_tmp.find(tmp) != mp_tmp.end()) {
                    mp_tmp[tmp]--;

                    if (mp_tmp[tmp] == 0)
                        mp_tmp.erase(tmp);
                    if (mp_tmp.empty()) {
                        res.push_back(l); 
                        // update l
                        mp_tmp[s.substr(l, word_len)]++;
                        l += word_len;
                    }

                } else {
                    if (mp.find(tmp) == mp.end()) { // the key is not in words
                        l = r + word_len;
                        mp_tmp = mp;
                    } else {
                        string str_l = s.substr(l, word_len);
                        while (str_l != tmp) {
                            mp_tmp[str_l]++;
                            l += word_len;
                            str_l = s.substr(l, word_len);
                        }
                        l += word_len;
                    }
                }
            }
        }
        return res;
    }
};