# 30.串联所有单词串

## 问题描述
[30.串联所有单词串](https://leetcode.cn/problems/substring-with-concatenation-of-all-words/description/)

## 解题思路
首先，由于`words`中所有字符串长度相同，要比较`words`与`s`:
    - `s`从`i = 0`开始，可以划分为一系列的长为`word_len = words[0].size()`的单词;
    - `s`从`i = 1`开始，可以划分为一系列的长为`word_len = words[0].size()`的单词;
    - ......
    - `s`从`i = word_len - 1`开始......

然后要注意利用`unordered_map<string, int>`判断是否满足条件的细节，`mp`用于判断`word`是否在`words`中;

`mp_tmp`的键值对中，如果值为0，就删掉该键;

还要注意`l`的处理，分为在`mp_tmp`为空，和`mp_tmp`不为空，但是`word`已经出现了超过`words`中的次数.

## 代码
```cpp
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], 对每一个i组成的单词序列，都单独使用滑动窗口法判断
        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);
                // 单词在words中
                if (mp_tmp.find(tmp) != mp_tmp.end()) {
                    mp_tmp[tmp]--;
                    // 说明出现了超过words里单词的数量
                    if (mp_tmp[tmp] == 0)
                        mp_tmp.erase(tmp);
                    if (mp_tmp.empty()) {
                        res.push_back(l); // 说明找到了目标
                        // mp_tmp = mp; // map变成新的
                        mp_tmp[s.substr(l, word_len)]++;
                        l += word_len;
                    }

                } else {
                    if (mp.find(tmp) == mp.end()) { // 说明这个单词不在words里面
                        l = r + word_len;
                        mp_tmp = mp;
                    } else { // word出现次数超过words中对应单词的次数了，在mp中而不在mp_tmp中
                        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;
    }
};
```