【LeetCode】30.串联所有单词的子串

串联所有单词的子串

题目描述：

给定一个字符串 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"] 顺序排列的连接。

思路分析：

滑动窗口法

什么是滑动窗口法？

滑动窗口，可以用来解决一些查找满足一定条件的连续区间的性质（长度等）的问题。由于区间连续，因此当区间发生变化时，可以通过旧有的计算结果对搜索空间进行剪枝，这样便减少了重复计算，降低了时间复杂度。往往类似于“请找到满足xx的最x的区间（子串、子数组）的xx”这类问题都可以使用该方法进行解决。

一般滑动窗口维护两个指针，左指针和右指针。

当窗口内的元素未达到题目条件时，右指针右移，探索未知的区间来满足条件
当窗口内的元素达到题目条件时，左指针右移，压缩区间，使窗口尽可能短得满足题目条件

滑动窗口常规模板：

int slidingWindow(vector<int> nums) {
    int n = nums.size();
    int ans = 0;
    // 记录窗口内的元素及其个数，非必要
    map<int, int> um;
    // l：窗口左边界； r：窗口右边界
    int l = 0, r = 0;
    // r 指针负责探索新的区间，直到搜索到nums的某末尾
    while (r < n) {
        um[r]++;
        // 如果区间不满足条件，l指针右移，窗口收缩
        while(区间 [l, r] is Invalid) {
            um[l]--;
            l++;
        }
        // 此处处理结果, deal with(ans, 区间[l, r])
        res = max(ans, r - l + 1); // 或者res = min(ans, r - l + 1);
        // 右指针右移，继续搜索
        r++;
    }
    return ans;
}

代码实现注解：

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        // 单词的数量
        int allCount = words.length;
        // 单个单词的长度
        int aloneLen = words[0].length();
        List<Integer> ret = new ArrayList<>();
        //当遍历长度超过整个字符串的长度推出循环
        for (int i = 0; i < aloneLen; i++) {
            //Map集合获取键值对，map表示滑动窗口中的单词频次和words中的单词频率之差，string收集在words中出现的单词，int收集出现频率
            Map<String, Integer> map = new HashMap<>();
            //遍历words中的word，对窗口里的每个单词计算差值
            for (String word : words) {
                map.put(word, map.getOrDefault(word, 0) + 1);
            }
            // 左边界，起始下标
            int left = i;
            // 右边界
            int right = i;
            // 当前匹配上的单词数量
            int curCount = 0;
            //开始滑动窗口
            while (right <= s.length() - aloneLen) {
                //code用来存放即将进入窗口的单词
                String code = s.substring(right, right + aloneLen);
                //用于计录该单词需要的次数
                Integer cnt = map.getOrDefault(code, 0);
                if (cnt > 0) {
                    // 右边的单词滑进来，并减数量
                    curCount++;
                    map.put(code, cnt - 1);
                    right += aloneLen;
                    if (curCount == allCount) {
                        ret.add(left);
                    }
                } else {
                    // 如果没有剩余且有消耗，左边的单词滑出去
                    if (curCount > 0) {
                        String preCode = s.substring(left, left + aloneLen);
                        map.put(preCode, map.get(preCode) + 1);
                        left += aloneLen;
                        curCount--;
                    } else {
                        // 这里增长 aloneLen，是一个单词的长度
                        left += aloneLen;
                        right += aloneLen;
                    }
                }
            }
        }
        return ret;
    }
}