30. 串联所有单词的子串-Toy模板网

这篇具有很好参考价值的文章主要介绍了30. 串联所有单词的子串。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

30. 串联所有单词的子串

题目链接：30. 串联所有单词的子串

代码如下：文章来源地址https://www.toymoban.com/news/detail-802149.html

//参考leetcode官方题解
class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> res;
        
        int sLen=s.size(),wordsLen=words.size(),wordLen=words[0].size();

        for(int i=0;i<wordLen&&i+wordLen*wordsLen<=sLen;i++)
        {   
            unordered_map<string,int> differ;
            //将该组第一个窗口内单词全部放入map中
            for(int j=0;j<wordsLen;j++)
            {
                differ[s.substr(i+j*wordLen,wordLen)]++;
            }

            //计算第一个窗口的单词与单词表中单词的频次差
            for(int i=0;i<words.size();i++)
            {
                if(--differ[words[i]] == 0)
                    differ.erase(words[i]);
            }

            //开始滑动窗口
            for(int start=i;start<sLen-wordLen*wordsLen+1;start+=wordLen)
            {
                //非第一个窗口
                if(start!=i)
                {
                    string word=s.substr(start+(wordsLen-1)*wordLen,wordLen);
                    if(++differ[word]==0)
                        differ.erase(word);

                    //右边单词划出窗口
                    word=s.substr(start-wordLen,wordLen);
                    if(--differ[word]==0)
                        differ.erase(word);
                }

                if(differ.empty())
                {
                    res.push_back(start);
                }
            }
        }

        return res;
    }
};