30.串联所有单词的子串

链接：30.串联所有单词的子串
难度：Hard
标签：哈希表、字符串、滑动窗口
简介：给定一个字符串 s 和一些 长度相同 的单词 words 。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。

题解 1 - cpp

• 编辑时间：2022-06-23
• 执行用时：172ms
• 内存消耗：28.3MB
• 编程语言：cpp
• 解法介绍：检测每一个可能成功的点。

class Solution {
   public:
    int wordSize, sSize, wordsSize;
    unordered_map<string, int> m;
    string s;
    vector<string> words;
    vector<int> findSubstring(string s, vector<string> &words) {
        this->s = s;
        this->words = words;
        sSize = s.size();
        wordSize = words[0].size();
        wordsSize = words.size();
        for (auto &w : words) m[w]++;
        vector<int> ans, list = getlist();
        unordered_map<int, int> listmap;
        for (int i = 0; i < list.size(); i++) listmap[list[i]] = i;
        for (int i = 0; i < list.size(); i++)
            if (check(list, listmap, i)) ans.push_back(list[i]);
        return ans;
    }
    vector<int> getlist() {
        vector<int> list;
        string tmp = s.substr(0, wordSize);
        for (int i = wordSize; i < sSize; i++) {
            if (m.count(tmp)) list.push_back(i - wordSize);
            tmp = tmp.substr(1, wordSize - 1) + s[i];
        }
        if (m.count(tmp)) list.push_back(sSize - wordSize);
        return list;
    }
    bool check(vector<int> &list, unordered_map<int, int> &listmap, int start) {
        int firstIdx = list[start];
        int lastIdx = firstIdx + (wordsSize - 1) * wordSize;
        if (!listmap.count(lastIdx)) return false;
        return _check(list, listmap, start, m);
    }
    bool _check(vector<int> &list, unordered_map<int, int> &listmap, int start,
                unordered_map<string, int> m) {
        for (int i = list[start], cnt = 0; cnt < wordsSize;
             cnt++, i += wordSize) {
            if (!listmap.count(i)) return false;
            if (m[s.substr(list[listmap[i]], wordSize)]-- == 0) return false;
        }
        return true;
    }
};