leetcode 第 30 题： 串联所有单词的子串(C++)

30. 串联所有单词的子串 - 力扣（LeetCode）

滑动窗口法，注意窗口大小是固定的，就是words中所有单词的总长度，而words中单词也是等长的。

和这个很像：

leetcode 第 438 题：找到字符串中所有字母异位词(C++)_qq_32523711的博客-CSDN博客

关于滑动窗口;

leetcode 第 76 题：最小覆盖子串(C++)_qq_32523711的博客-CSDN博客

找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置：这句话可以理解为该子串是words中单词的排列，而我们要做的就是找出所有是words中单词排列的子串（的起始位置）。

关于排列;

leetcode 第 567 题：字符串的排列(C++)_qq_32523711的博客-CSDN博客

首先上比较暴力一点的解法，从左到右一个窗口一个窗口的统计，统计使用哈希表，执行效率一般：

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        if(s.empty() || words.empty()) return {};
        vector<int> res;
        unordered_map<string, int> need, window;
        for(auto c : words) ++need[c];
        int len = words[0].size(); //单词长度
        int len_words = words.size()*len;

        for(int i = 0; i+len_words <= s.size(); ++i){
            int count = 0;
            for(int j = i; j < i+len_words; j += len){
                auto str = s.substr(j, len);
                if(need.count(str)){
                    ++window[str];
                    if(need[str] == window[str])  ++count;
                    if(need[str] < window[str]) break;
                }else
                    break;
            }
            if(count == need.size()) res.push_back(i);
            window.clear();
        }
        return res;
    }
};
           

不过发现了一个易错点:for循环判断条件：

for(int i = 0; i+len_words <= s.size(); ++i)
           

不能写为：

for(int i = 0; i<= s.size() - len_words ; ++i)
           

原因是s.size()得到无符号数，而int型为有符号的，使用减法会出现溢出（没有深究这儿）。

然后一开始是想套滑动窗口的模板的，但是过程不是那么顺利，因为139个测试用例卡住了：

"ababaab"
["ab","ba","ba"]
输出：[0,1]
预期：[1]
           

因为我右边界是逐个增加的，所以aba这样的他就认为即会包含ab也会包含ba，所以就错误了，代码认为ababaa是匹配的，但是实际不匹配。所以代码主要错误就是会把一些不匹配的也找出来（当然正确的也能找出来），解决办法嘛，我就又加了一个

check

函数来判断到底匹不匹配：

但是执行效率还是一般，这个check挺耗时的：

class Solution {
public:
    bool check(const string &s, unordered_map<string, int> need, int left, int right, int len){
	    int count = 0;
	    for (int i = left; i < right; i = i + len){
		    auto str = s.substr(i, len);
		    if (need.count(str)){
			    --need[str];
			    if (need[str] == 0)	++count;
		    }
		    else return false;
	    }
	    return count == need.size();
    }
    vector<int> findSubstring(string s, vector<string>& words) {
        if(!s.size() || !words.size()) return {};
        vector<int> res;
        unordered_map<string, int> need;
        for(auto c : words) ++need[c];
        auto test = need;
        int left = 0, right = 0;
        int len = words[0].size(); //单词长度
        int count = 0; //记录需要查全的字符串个数
        while(right < s.size() - len + 1){
            auto str = s.substr(right, len);
            ++right; //right右移
            if(need.count(str) > 0){
                --need[str];
                if(need[str] == 0)  ++count;
            }
            if(right - 1 - left == (words.size() - 1) * len){
                if(count == need.size()){
                    if(check(s, test, left, right, len))
                        res.push_back(left);
                }
                auto str = s.substr(left, len);
                ++left;
                if(need.count(str) > 0){
                    if(need[str] == 0)  --count;
                    ++need[str];
                }
            }
        }
        return res;
    }
};
           

最后参考了这位兄弟的题解：

串联所有单词的子串 - 串联所有单词的子串 - 力扣（LeetCode）

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        if(s.empty() || words.empty()) return {};
        vector<int> res;
        unordered_map<string, int> need;
        for(auto c : words) ++need[c];
        int len = words[0].size(); //单词长度
        int len_words = words.size()*len;

        //右边界每次增加len，i=0的时候，这一轮就只能遍历到 i+len*n(n为整数) 开头的子串
        // i 从 0 ～ len-1，就能遍历到所有的子串了
        for(int i = 0; i < len; ++i){ 
            int left = i, right = i;
            int count = 0;
            unordered_map<string, int> window;
            while(right+len <= s.size()){
               auto str = s.substr(right, len);
               right += len;

               if(need.count(str) == 0){//该单词不在words中，重置计数器、边界以及window
                    count = 0;
                    left = right;
                    window.clear();
               }else{
                   ++window[str];
                   ++count;
                   while(window[str] > need[str]){ //次数过多也要需要缩小窗口，因为每个单词的次数都应该是刚好的
                       auto tmp = s.substr(left, len);
                       --count;
                       --window[tmp];
                       left += len;
                   }
                   if(count == words.size())    res.push_back(left);
               }
           }
       }
        return res;
    }
};