30.substring-with-concatenation-of-all-words 串联所有单词串

问题描述

30.串联所有单词串

解题思路

首先，由于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中的次数.

代码

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;
    }
};