leetcode 30. 串联所有单词的子串 | 困难难度

1. 题目详情

给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。

s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。

例如，如果 words = [“ab”,“cd”,“ef”]， 那么 “abcdef”， “abefcd”，“cdabef”， “cdefab”，“efabcd”， 和 “efcdab” 都是串联子串。 “acdbef” 不是串联子串，因为他不是任何 words 排列的连接。
返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。

示例 1：
输入：s = “barfoothefoobarman”, words = [“foo”,“bar”]
输出：[0,9]
解释：因为 words.length == 2 同时 words[i].length == 3，连接的子字符串的长度必须为 6。
子串 “barfoo” 开始位置是 0。它是 words 中以 [“bar”,“foo”] 顺序排列的连接。
子串 “foobar” 开始位置是 9。它是 words 中以 [“foo”,“bar”] 顺序排列的连接。
输出顺序无关紧要。返回 [9,0] 也是可以的。

示例 2：
输入：s = “wordgoodgoodgoodbestword”, words = [“word”,“good”,“best”,“word”]
输出：[]
解释：因为 words.length == 4 并且 words[i].length == 4，所以串联子串的长度必须为 16。
s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。
所以我们返回一个空数组。

示例 3：
输入：s = “barfoofoobarthefoobarman”, words = [“bar”,“foo”,“the”]
输出：[6,9,12]
解释：因为 words.length == 3 并且 words[i].length == 3，所以串联子串的长度必须为 9。
子串 “foobarthe” 开始位置是 6。它是 words 中以 [“foo”,“bar”,“the”] 顺序排列的连接。
子串 “barthefoo” 开始位置是 9。它是 words 中以 [“bar”,“the”,“foo”] 顺序排列的连接。
子串 “thefoobar” 开始位置是 12。它是 words 中以 [“the”,“foo”,“bar”] 顺序排列的连接。

提示：
1 <= s.length <= 104
1 <= words.length <= 5000
1 <= words[i].length <= 30
words[i] 和 s 由小写英文字母组成

1. 原题链接

leetcode 30. 串联所有单词的子串

2. 基础框架

● Cpp代码框架

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {

    }
};

2. 解题思路

1. 题目分析

$(1)$ 本题给出一个字符串s和字符串数组words，且words中字符串的长度相同，这是很关键的一句话。找出s的所有子串中是words串联子串的起始下标。串联子串就是words的字符串以任意顺序排列形成的字符串。注意排列的单位是字符串，而不是字符，且这些字符串长度相等。
如果题目没有words中字符串长度相等这句话，这道题将会变得很麻烦，因为串联子串的定义单位是字符串，但我们遍历的时候只能是一步一步的遍历，每次一个字符被加入s的以遍历子串中，并被记录在哈希表中。所以可能会出现这种情况：我们遍历的s中的子串字符频次是与words中所有字符串对应字符频次是相同的，但是并不满足串联子串的要求。

而题目中提示我们words的字符串长度都相同，我们把单个字符串的长度记为len。那么我们可以把s分成len个长度的一个个小区间，例如从0下标开始划分：[0, len-1] [len, 2*len-1] [2*len, 3*len-1]......，这样一直到s结束，把s划分成了区间，把s也看做由一个个小字符串组成的大字符串，遍历字符串s时，每次的步长是len，而不再是1。
s以len长度划分图-》

但是只进行一次划分是不够的，因为每次遍历的步长是len，所以会漏掉部分情况：比如[1, len]以及之后的情况。所以划分方式是分别以0、1、2...len-1为起始位置，进行长度为len的划分，这样就把所有的情况考虑到了。既然s被多次划分，所以也需要相同次数len次的遍历。

$(2)$ 对于暴力枚举：需要三层循环，外层循环len次，表示每次的s划分。内层经典两层循环，固定一个起始已划分位置left，right从left开始依次向右遍历已划分的s，每次步长是len。
两个哈希表的键值是<string, int>，哈希表1hash1记录words内字符串的频次，哈希表2hash2记录遍历的字符串的频次。在遍历的字符串个数等于words的字符串的个数，就判断两个哈希表是否相等，如果相等则当前遍历的子串[left, right+len - 1]就是符合题意的串联子串，否则就不是，且以right及其之后的所有位置为结束的子串都不会是串联子串，就没有遍历的必要了。left+=len以新的起始位置，同时right回退到新left位置，哈希表2hash清空，重新开始遍历。
$(3)$

2. 算法原理

$(1)$ 对于暴力枚举，right不需要每次都回退到left位置，哈希表2hash2也不需要每次都清空，再重新开始遍历。
滑动窗口：
每次right位置为结尾的子串不满足题意（串联子串）时，right不再回退，hash2不再清空，而是left每次右移len长度，同时以left为起始的len个长度的子串被移出哈希表2hash2。

初始m = words.size(), len = words[0].size(),ret是结果数组
$(2)$进窗口：hash2[s.substr(right, len)]++；
$(3)$判断：right-left+1 > m * len；
$(4)$出窗口：hash2[s.substr(left, len)]- -,left- -；
$(5)$更新结果：在right - left == (m - 1) * len，且两个哈希表hash1与hash2相等时
把left作为一个结果加入到结果ret数组内；

$(6)$对哈希表判断相等的优化：引入有效字符串计数count，作用是记录哈希表2hash2和哈希表1hash1都出现的字符串。
进窗口 + 维护count：in = s.substr(right,len) ;hash2[in]++;hash2[in] <= hash1[in]时进入的是有效字符，count++；
判断：right-left+1 > m*len时
出窗口 + 维护count：out = s.substr(left,len);hash2[out] <= hash1[out] 时移除的是有效字符，count–；hash2[out]–;
更新结果：count == m时，把left加入到结果数组ret中；

3. 时间复杂度

暴力枚举 $O(n^2/len)$

字符串s长度为n，words内字符串长度为len，划分成了n/len个组，共进行了len次划分，故循环次数$len\ast n/len\ast n/len==n^2/len$

滑动窗口 $O(n)$

$len\ast n/len==n$

3. 代码实现

滑动窗口，并使用遍历判断两个哈希表是否相等

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> ret;
        unordered_map<string, int> hash1;
        for(auto& e : words) hash1[e]++;//记录words内字符串的频次
        
        int n = s.size();
        int len = words[0].size();
        int m = words.size();

        for(int i = 0; i < len; i++){//以len对s进行划分，不同的划分方式是len种，即分别以0,1,2,...,len-1为起始的划分
            int l = i, r = i;//滑动窗口初始化
            unordered_map<string, int> hash2;
            while(r + len <= n){//r的步长是len，所以需要防止越界访问
                string in = s.substr(r, len);//切割得到子串
                hash2[in]++;//进窗口
                while(r - l + 1 > len * m){//判断窗口内字符个数是否超过words内所有字符个数
                    string out = s.substr(l, len);
                    hash2[out]--;//出窗口
                    //if(hash2[out] == 0) hash2.erase(out);
                    l += len;
                }
                if(r - l == (words.size() - 1) * len){//更新结果
                    int flag = 1;
                    for(auto& str : words){//判断两个哈希表是否相等
                        if(hash1[str] != hash2[str]){
                            flag = 0;
                            break;
                        }
                    }
                    if(flag) ret.push_back(l);
                }
                r += len;//为下一次元素进窗口做准备
            }
        }
        return ret;
    }
};

滑动窗口，引入有效字符计数count

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int>ret;
        unordered_map<string, int> hash1;
        for(auto& e : words) hash1[e]++;// 记录字符串频次
        int n = s.size();
        int m = words.size();
        int len = words[0].size();
        
        for(int i = 0; i < len; ++i){
            int l = i, r = i;
            unordered_map<string, int> hash2;
            int count =  0;
            while(r + len <= n){
                // 进窗口，维护count
                string in = s.substr(r, len);
                hash2[in]++;
                if(hash1.count(in) && hash2[in] <= hash1[in]) count++;
                // 判断
                while(r - l + 1 > len * m){
                    // 出窗口，维护count
                    string out = s.substr(l, len);
                    if(hash1.count(out) && hash2[out] <= hash1[out]) count--;
                    hash2[out]--;
                    l += len;
                }
                // 更新结果
                if(count == m) ret.push_back(l);
                r += len;
            }
            
        }
        return ret;
    }
};

4. 知识与收获

$(1)$ 本题关键的一点：words内字符串长度相等，这样就可以依此把字符串作为整体，把s划分成一个个的子串，进行遍历操作了。

---

$The$ $End$