给定一个字符串 s 和一些 长度相同 的单词 words 。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。

注意子串要与 words 中的单词完全匹配，中间不能有其他字符 ，但不需要考虑 words 中单词串联的顺序。

示例 1：
输入：s = "barfoothefoobarman", words = ["foo","bar"]
输出：[0,9]
解释：
从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。
输出的顺序不重要, [9,0] 也是有效答案。

示例 2：
输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
输出：[]

示例 3：
输入：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
输出：[6,9,12]

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/substring-with-concatenation-of-all-words
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路及方法

我看了官方题解，不是很懂，在看了一下其他作者的体节后，结合自己的思想，写出了应该算是滑动窗口解法的题解吧。

我把s中恰好可以由words中所有单词串联形成子串的对比单独写了一个方法，用了map计数，简单易懂。该方法传进来的参数有两个，一个是s的子串，一个是字符串数组words。

• 首先用map记录words中每个字符串出现的次数，然后对s的字串进行滑动窗口，每一次滑动移动步数为step，即words数组元素的长度；
• 然后将子串中出现的字符串在map中进行参照，出现则次数-1，未出现则代表words不能组成该子串；
• 接着判断map中出现次数为0的字符串，进行删除操作；
• 最后判定map是否为空，为空则代表该子串可以由 words 中所有单词串联形成。
  最后的最后，就是对原始字符串s进行滑动窗口。

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res = new ArrayList<>();
        int len = words.length * words[0].length();
        // 从首位开始遍历，寻找所有符合条件的字串起始位
        for (int i = 0; i <= s.length() - len; i++) {
            String cur = s.substring(i, i + len);
            if (isEquals(cur, words)) res.add(i);
        }

        return res;
    }

    /**
     * @description: 判断字符串s是否由words内字符串完全充分构成
     * @author: Abean
     * @date: 2022/7/15 15:50
     * @param: [s, words]
     * @return: 若参照map为空，则证明字符串s由words内字符串完全充分构成，返回true，否则false
     **/
    public Boolean isEquals(String s, String[] words) {
        Map<String, Integer> refer = new HashMap<>();
        // 统计words字符串次数
        for (String str : words) {
            refer.put(str, refer.getOrDefault(str, 0) + 1);
        }

        // 对比cur字符串中子串出现次数
        int n = s.length();
        int step = words[0].length();
        for (int i = 0; i <= n - step; i += step) {
            String cur = s.substring(i, i + step);
            // 出现则次数减一，否则输入字符串不由words数组内字符串组成
            if (refer.containsKey(cur)) {
                refer.put(cur, refer.get(cur) - 1);
            } else {
                return false;
            }
            // 若次数为0，删除该子串
            if (refer.get(cur) == 0) refer.remove(cur);
        }

        return refer.size() == 0;
    }
}

结果如下：