030.串联所有单词的子串

作者：沉默王二
发布时间：2024-02-27T16:25:14.890+0800

---

鲁迅曾说，人生就是一道道关，闯过去了，你就进阶了，闯不过去，你就原地踏步。年后这段时间不仅是春招、日常实习、社招都在同步进行，大家一定要抓紧时间。就算是离秋招，25 届也没有多少时间了，顶多 5 个月。每天一道二哥的 LeetCode 刷题笔记，继续进步。

技术派阅读地址：https://paicoding.com/column/7/ 30

• 语雀专栏地址+密码可通过星球置顶帖查看：https://t.zsxq.com/15rEo9Pdu

• 这道题可以说完全重写了，给出 4 道大家完全都能掌握的题解（ 暴力算法「2 种」+滑动窗口「2种」，写了几乎一天的时间，累死）。

• 增加代码注释，这样大家更容易看懂并掌握题解；

• 增加参考资料，这样大家可以从零基础直接开刷，减轻新手刷题的阻力；

• 增加手绘图，这样大家更容易理解解题思路；

• 增加 ACM 输入输出，这样大家可以在 Intellij IDEA 中进行调试；

• 增加题解模拟，这样大家可以根据题解模拟整个题解过程，看完会有一种“哦哦”恍然大悟的感觉；

• 图片上传至 OSS 并配合 CDN，提升大家在技术派网站中的阅读体感。

• 另外，这一版本会作为 PDF 的终稿随后在星球进行发布。

题意

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

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

例如，如果 words = ["ab","cd","ef"]， 那么 "abcdef"， "abefcd"，"cdabef"， "cdefab"，"efabcd"， 和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串，因为他不是任何 words 排列的连接。

返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。

难度

困难

示例

输入：s = "barfoothefoobarman", words = ["foo","bar"]

解释：因为 words.length == 2 同时 words[i].length == 3，连接的子字符串的长度必须为 6。子串 "barfoo" 开始位置是 0。它是 words 中以 ["bar","foo"] 顺序排列的连接。子串 "foobar" 开始位置是 9。它是 words 中以 ["foo","bar"] 顺序排列的连接。输出顺序无关紧要。返回 [9,0] 也是可以的。
输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]输出：[]解释：因为 words.length == 4 并且 words[i].length == 4，所以串联子串的长度必须为 16。s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。所以我们返回一个空数组。
输入：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

这道题，说实话，一开始看上去是有点懵逼的，因为描述了一大堆，有点抓不到重点。

以前版本的 LeetCode 描述中，例子也没有，我第一次看上去，确实有点摸不着头脑。

最新的 LeetCode 版本中加入了例子和解释，就清晰多了。

首先我们来搞清楚一个概念，什么是串联子串？

比如说一个字符串 s = abc，words = ["a","b","c"]。

words 所能组成的串联子串有：

• abc
• bac
• cab
• acb
• bca
• cba

然后，我们再来判断这些串联子串是否在 s 中，如果在的话，就返回它的起始位置。

那么显然，串联子串 abc 在 s 中，起始位置是 0。别的串联子串就不在。

那么很容易就能想到一种暴力解法，先排列组合出所有的串联子串，然后在 s 中查找这些子串，如果找到了，就记录它的起始位置。

①、我们使用 Guava 的 Collections2.permutations 方法来生成所有 words 的排列。借助 API 可以帮我们减轻排列组合的工作量，当然了，也可以直接使用回溯算法来完成。

// 生成 words 的所有排列

List<String> permutations = new ArrayList<>();
// 把数组转成集合    List<String> list = new ArrayList<>();    Collections.addAll(list, words);
// 生成所有排列    for (List<String> permutation : Collections2.permutations(list)) {        StringBuilder sb = new StringBuilder();        for (String word : permutation) {            sb.append(word);        }        permutations.add(sb.toString());    }
return permutations;}

比如说，我们有一个 words = ["foo","bar"]，那么我们可以生成所有的排列：

• foobar
• barfoo

当然了，这里也可以使用回溯算法来完成，代码如下：

class PermutationsGenerator {

// 生成所有排列的方法    public List<String> generatePermutations(String[] words) {        List<String> results = new ArrayList<>();        permute(words, 0, results);        return results;    }
// 辅助方法：递归地生成排列    private void permute(String[] array, int start, List<String> result) {        if (start >= array.length) {            // 将当前排列转换为字符串并添加到结果列表            result.add(String.join("", array));        } else {            for (int i = start; i < array.length; i++) {                swap(array, start, i); // 交换元素                permute(array, start + 1, result); // 递归地生成剩余元素的排列                swap(array, start, i); // 撤销交换            }        }    }
// 交换数组中的两个元素    private void swap(String[] array, int i, int j) {        String temp = array[i];        array[i] = array[j];        array[j] = temp;    }
public static void main(String[] args) {        PermutationsGenerator generator = new PermutationsGenerator();        String[] words = {"a", "b", "c"};        List<String> permutations = generator.generatePermutations(words);        System.out.println("排列组合: " + permutations);    }}

②、然后我们再来检查每个排列是否为 s 的子串。判断子串就比较简单了，直接使用 indexOf 方法就可以了。

当然了，一次 indexOf 是不够的，容易漏掉所有的情况，所以要使用 while 循环配合 indexOf 的重载方法 index = s.indexOf(permutation, index + 1)来完成。

public List findSubstring(String s, String[] words) {

List<Integer> result = new ArrayList<>();    // 生成所有 words 的排列    List<String> permutations = generatePermutations(words);    // 检查每个排列是否为 s 的子串    for (String permutation : permutations) {        int index = s.indexOf(permutation);        while (index != -1) {            // 如果找到，添加到结果列表中            if (!result.contains(index)) {                result.add(index);            }            // 继续查找下一个匹配的子串            index = s.indexOf(permutation, index + 1);        }    }
return result;}

不过，由于这个暴力解法的效率很低，我们就直接使用 ACM 的模式在 Intellij IDEA 中进行尝试了。这样方便帮助大家理解整个题解的过程。

class Main03001 {

    Solution03001 solution = new Solution03001();        String s = "barfoobarfoothefoobarman";        String[] words = {"foo", "bar"};        List<Integer> result = solution.findSubstring(s, words);        System.out.println(result);    }

}
class Solution03001 { public List findSubstring(String s, String[] words) { // 这是 LeetCode 的第 30 题 List result = new ArrayList<>(); // 生成所有 words 的排列 List permutations = generatePermutations(words); // 检查每个排列是否为 s 的子串 for (String permutation : permutations) { int index = s.indexOf(permutation); while (index != -1) { // 如果找到，添加到结果列表中 if (!result.contains(index)) { result.add(index); } // 继续查找下一个匹配的子串 index = s.indexOf(permutation, index + 1); } }
return result; }
// 生成 words 的所有排列 private List generatePermutations(String[] words) { List permutations = new ArrayList<>();
// 把数组转成集合 List list = new ArrayList<>(); Collections.addAll(list, words);
// 生成所有排列 for (List permutation : Collections2.permutations(list)) { StringBuilder sb = new StringBuilder(); for (String word : permutation) { sb.append(word); } permutations.add(sb.toString()); }
return permutations; }}

来看一下运行结果：

[3,15,0,6]

也是完全可以找出来的，不过，很遗憾，如果直接在 LeetCode 上用这种方法来完成的话，会超出时间限制。

但是，刷 LeetCode 其实并不只是为了刷题，更重要的是要学会分析问题，尤其是对于算法基础比较薄弱的球友，如果一上来就搞效率很高的解法，但看又看不懂，那就没有意义了。

分析 2

那我们接着来分析，看看能不能在暴力的基础上进一步优化，这次我们就不排列组合了，因为排列组合确实会比较花费时间，尤其是当 words 数组长度比较大的时候。

这次采用逆向思维。

第一步，我们直接在 s 中先截取一个长度为 words.length * words[0].length 的子串（words 数组中的字符串长度都相等），那么这个子串要么是串联子串，要么就不是，对吧？

第二步，再从这个子串中截取长度为 words[0].length 的子串，然后判断这个子串是否在 words 数组中，如果在的话，就继续截取下一个子串，直到截取完毕。

我们借助了两个哈希表来帮我们完成这项工作：

①、一个哈希表 cnt 用于记录 words 中每个单词应出现的次数，比如说：

• words = ["foo","bar"]，那么 cnt = {foo=1, bar=1}。
• words = ["foo","bar","foo"]，那么 cnt = {foo=2, bar=1}。

并且哈希表 cnt 的 key 还可以帮我们判断第二步中当前截取的子串是否在 words 数组中。

不在的话，就可以直接跳过这次循环了。

②、一个哈希表 com 用于记录当前考察的子串中各单词的出现次数

如果 com 中统计到的单词出现次数超过了它在 words 中应有的次数，那么说明当前子串不符合条件，立即跳出。

最后，如果 com 中统计到的和 cnt 完全一样，那么说明当前子串是符合条件的，将其起始索引添加到结果列表中。

我们来看一下完整的题解代码：

class Solution {

    List<Integer> res = new ArrayList<>();        if (s == null || words == null || words.length == 0) return res;
    // 单词的长度，假设所有单词长度相同        int wordLength = words[0].length();        // 所有单词串联起来的总长度        int allWordsLength = wordLength * words.length;        // 使用 cnt 哈希表来记录 words 中每个单词应出现的次数        Map<String, Integer> cnt = new HashMap<>();        for (String word : words) {            cnt.put(word, cnt.getOrDefault(word, 0) + 1);        }
    // 遍历字符串 s，考虑每一个可能的起始位置        for (int i = 0; i <= s.length() - allWordsLength; i++) {            // com 哈希表用于记录当前考察的子串中各单词的出现次数            Map<String, Integer> com = new HashMap<>();            // 提取从 i 开始长度为 allWordsLength 的子串            String temp = s.substring(i, i + allWordsLength);            boolean isValid = true; // 标记当前子串是否有效            // 再次遍历子串，每次移动一个单词的长度            for (int j = 0; j < temp.length(); j += wordLength) {                String t = temp.substring(j, j + wordLength);                // 如果 t 不在 cnt 中，说明当前子串不符合条件，立即跳出                if (!cnt.containsKey(t)) {                    isValid = false;                    break;                }                com.put(t, com.getOrDefault(t, 0) + 1);                // 如果当前单词 t 的出现次数超过了它在 words 中应有的次数，同样说明当前子串不符合条件                if (com.get(t) > cnt.get(t)) {                    isValid = false;                    break;                }            }            // 如果子串有效，将其起始索引添加到结果列表中            if (isValid && com.equals(cnt)) {                res.add(i);            }        }        return res;    }}

虽然题解效率并不乐观，但很好理解，对吧？

分析 3

我们来观察一下分析 2 中的过程：

对于每个长度为 6 的子串（words = ["foo","bar"]），我们都要检验一次，但是可以注意到，第一次和第四次，本质上就是去掉了一个bar加上一个the，第二次和第五次，本质上就是去掉了一个arf加上一个hef，第三次和第六次，本质上就是去掉了一个rfo加上了一个efo。

所以……我们可以考虑将他们分成单词长度组来看看他们的性质？

分组之后，每次只需要添加一个单词，再删去一个单词就可以得到了下一次的状态，这样子就不用费劲的重新构造这个字符串了。

每次添加一个单词和删去一个单词的代价也不高！

其实这样子就相当于设立了一个窗口，在字符串s上，以单词长度/每次的速度在移动，所以这也经常被称作滑动窗口。

我们在**003.无重复字符的最长子串 **中也曾详细讲过滑动窗口，其核心原理就在于利用滑动的窗口减少不必要的计算。

但其实思路和分析 2 的差不多，只是在实现上有所不同。

第一步，同样是遍历 s，准备一个滑动窗口，对窗口内的子串进行验证。

for (int i = 0; i }

因为是滑动窗口，所以第一个 for 循环只需要遍历 0 到 wordLen - 1 这个范围，见下图的三个红色框。如果 wordLen = 3，那么就是遍历 0、1、2 这三个位置，后续的处理交给滑动窗口。

![图片](https://clxhxhhr.top/uploads/weblog/erge/erge_lc_image_33.png)

第二步，在窗口内部，每次滑动的步长为一个单词的长度 j += wordLength;start += wordLength;，滑动窗口的宽度为所有单词的总长度 s.length() - windowLength。

for (int j = i; j // 处理一个窗口内的所有单词
// 左窗口右移一个单词的长度 start += wordLength; }}

如果窗口内的单词正好匹配 words 数组中的所有单词，则添加到结果中。

if (start == end) {

}

来看完整的题解：

class Solution {

    List<Integer> result = new ArrayList<>();        if (s == null || words == null || words.length == 0) return result;                // 创建一个HashMap来存储words数组中每个单词的出现次数        Map<String, Integer> wordCount = new HashMap<>();        for (String word : words) {            wordCount.put(word, wordCount.getOrDefault(word, 0) + 1);        }                // 单个单词的长度和窗口的长度（所有单词的总长度）        int wordLength = words[0].length();        int windowLength = words.length * wordLength;                // 遍历字符串s，每次增加的步长为一个单词的长度        for (int i = 0; i < wordLength; ++i) {            for (int j = i; j <= s.length() - windowLength; j += wordLength) {                // 用于记录当前窗口中单词的出现情况                Map<String, Integer> seenWords = new HashMap<>();                int start = j;                int end = j + windowLength;                                // 在窗口内部，每次也是按照单词的长度来切分和检查                while (start < end) {                    String currentWord = s.substring(start, start + wordLength);                    seenWords.put(currentWord, seenWords.getOrDefault(currentWord, 0) + 1);                                        // 如果当前单词不在words中，或者出现的次数超过了words中该单词的次数，则跳出循环                    if (!wordCount.containsKey(currentWord) || seenWords.get(currentWord) > wordCount.get(currentWord)) {                        break;                    }                    start += wordLength;                }                                // 如果窗口内的单词正好匹配words数组中的所有单词，则添加到结果中                if (start == end) {                    result.add(j);                }            }        }                return result;    }}

在这个题解中，同样借助了两个 HashMap 来帮助我们完成这项工作。

①、一个 HashMap wordCount 用于记录 words 数组中每个单词应出现的次数。

②、一个 HashMap seenWords 用于记录当前窗口中单词的出现情况。

也很好理解，大家看完代码注释就明白为什么了，来看一下题解效率：

显然比之前的效率提高了不少，对吧？

分析 4

我们再来看一种解法，这种解法是在分析 3 的基础上进一步优化的。

class Solution {

    List<Integer> res = new ArrayList<>();        if (s == null || words == null || s.length() == 0 || words.length == 0) return res;
    int wordLen = words[0].length(); // 单词的长度        int wordCount = words.length; // 单词的数量
    // 统计words中每个单词应该出现的次数        Map<String, Integer> wordMap = new HashMap<>();        for (String word : words) {            wordMap.put(word, wordMap.getOrDefault(word, 0) + 1);        }
    // 遍历所有的可能起始位置，0 到 wordLen - 1        for (int i = 0; i < wordLen; i++) {            int left = i; // 窗口左边界            int count = 0; // 窗口中符合条件的单词数量            Map<String, Integer> windowMap = new HashMap<>(); // 窗口中单词的计数
        // 移动窗口的右边界            for (int j = i; j <= s.length() - wordLen; j += wordLen) {                String word = s.substring(j, j + wordLen);
            // 如果word是有效的                if (wordMap.containsKey(word)) {                    windowMap.put(word, windowMap.getOrDefault(word, 0) + 1);                    count++;
                // 如果窗口中该单词的数量超过了应有的数量，需要调整窗口的左边界                    while (windowMap.get(word) > wordMap.get(word)) {                        String leftWord = s.substring(left, left + wordLen);                        windowMap.put(leftWord, windowMap.get(leftWord) - 1);                        count--;                        left += wordLen;                    }
                // 如果窗口中的单词数量正好等于words中的单词数量，记录起始位置                    if (count == wordCount) {                        res.add(left);                        // 移动左边界以寻找新的匹配                        String leftWord = s.substring(left, left + wordLen);                        windowMap.put(leftWord, windowMap.get(leftWord) - 1);                        count--;                        left += wordLen;                    }                } else {                    // 如果word不是有效的，则重置窗口                    windowMap.clear();                    count = 0;                    left = j + wordLen;                }            }        }        return res;    }}

分析 4 和分析 3 在解决问题的思路上都是一样，都是通过滑动窗口来遍历 s，然后在窗口内部，每次按照单词的长度来切分和检查。

但分析 4 采用了更细粒度的窗口移动策略，当遇到不匹配的单词时，它不是直接跳过整个窗口，而是逐个单词地调整窗口的左边界，直到窗口中的单词再次满足条件，或者窗口被完全重置。

这种策略的优势在于，它可以更快地找到下一个匹配的窗口，而不是直接跳过整个窗口。

所以效率也有了不少的提升，但实现比分析 3 复杂了不少。

总结

本题是一道 hard，但通过分析 1、分析 2、分析 3、分析 4 这么一套循序渐进的方式讲解下来，相信大家也都能够掌握了。

分析 1 非常直观，排列组合然后在 s 中查找，但效率不高。因为排列组合就需要花费很多时间。

分析 2 采用了逆向思维，先在 s 中截取一个长度为 words.length * words[0].length 的子串，然后再截取长度为 words[0].length 的子串，判断这个子串是否在 words 数组中，如果在的话，就继续截取下一个子串，直到截取完毕。这种方法效率就比分析 1 提高了一些。

分析 3 采用了滑动窗口的思想，也非常直观和容易掌握，效率也比分析 2 提高了不少。

分析 4 在分析 3 的基础上进一步优化，采用了更细粒度的窗口移动策略，效率提高了一大截，但代码量也多了不少。

好，我们来总结一下题解过程中所遇到的 Java 基础知识：

①、HashMap 的使用，包括 put、get、getOrDefault、clear 等方法的使用：HashMap 的深度解析

②、字符串的截取：Java 字符串截取

③、滑动窗口的使用：滑动窗口算法详解

力扣链接：https://leetcode.cn/problems/substring-with-concatenation-of-all-words/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100 天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

该题解目前只针对**二哥编程星球 **的球友开放，如果你也想一起打卡学习算法的话，扫下面的优惠券加入我们吧，星球目前 4500+ 人，定价 149 元，从当初的 99 元一路涨上来的，所以早就是优势，别再犹豫了。

（优惠券仅 300 张，数量有限）

一个人可以走得很快，但一群人才能走得更远。如果想去面中大厂的话，LeetCode 几乎是必刷的，二哥的 LeetCode 题解通俗易懂、图文并茂，理解给你举一反三的解题能力，冲鸭。

鲁迅曾说，人生就是一道道关，闯过去了，你就进阶了，闯不过去，你就原地踏步。年后这段时间不仅是春招、日常实习、社招都在同步进行，大家一定要抓紧时间。就算是离秋招，25 届也没有多少时间了，顶多 5 个月。每天一道二哥的 LeetCode 刷题笔记，继续进步。

技术派阅读地址：https://paicoding.com/column/7/ 30

• 语雀专栏地址+密码可通过星球置顶帖查看：https://t.zsxq.com/15rEo9Pdu

• 这道题可以说完全重写了，给出 4 道大家完全都能掌握的题解（ 暴力算法「2 种」+滑动窗口「2种」，写了几乎一天的时间，累死）。

• 增加代码注释，这样大家更容易看懂并掌握题解；

• 增加参考资料，这样大家可以从零基础直接开刷，减轻新手刷题的阻力；

• 增加手绘图，这样大家更容易理解解题思路；

• 增加 ACM 输入输出，这样大家可以在 Intellij IDEA 中进行调试；

• 增加题解模拟，这样大家可以根据题解模拟整个题解过程，看完会有一种“哦哦”恍然大悟的感觉；

• 图片上传至 OSS 并配合 CDN，提升大家在技术派网站中的阅读体感。

• 另外，这一版本会作为 PDF 的终稿随后在星球进行发布。

题意

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

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

例如，如果 words = ["ab","cd","ef"]， 那么 "abcdef"， "abefcd"，"cdabef"， "cdefab"，"efabcd"， 和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串，因为他不是任何 words 排列的连接。

返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。

难度

困难

示例

输入：s = "barfoothefoobarman", words = ["foo","bar"]

解释：因为 words.length == 2 同时 words[i].length == 3，连接的子字符串的长度必须为 6。子串 "barfoo" 开始位置是 0。它是 words 中以 ["bar","foo"] 顺序排列的连接。子串 "foobar" 开始位置是 9。它是 words 中以 ["foo","bar"] 顺序排列的连接。输出顺序无关紧要。返回 [9,0] 也是可以的。
输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]输出：[]解释：因为 words.length == 4 并且 words[i].length == 4，所以串联子串的长度必须为 16。s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。所以我们返回一个空数组。
输入：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

这道题，说实话，一开始看上去是有点懵逼的，因为描述了一大堆，有点抓不到重点。

以前版本的 LeetCode 描述中，例子也没有，我第一次看上去，确实有点摸不着头脑。

最新的 LeetCode 版本中加入了例子和解释，就清晰多了。

首先我们来搞清楚一个概念，什么是串联子串？

比如说一个字符串 s = abc，words = ["a","b","c"]。

words 所能组成的串联子串有：

• abc
• bac
• cab
• acb
• bca
• cba

然后，我们再来判断这些串联子串是否在 s 中，如果在的话，就返回它的起始位置。

那么显然，串联子串 abc 在 s 中，起始位置是 0。别的串联子串就不在。

那么很容易就能想到一种暴力解法，先排列组合出所有的串联子串，然后在 s 中查找这些子串，如果找到了，就记录它的起始位置。

①、我们使用 Guava 的 Collections2.permutations 方法来生成所有 words 的排列。借助 API 可以帮我们减轻排列组合的工作量，当然了，也可以直接使用回溯算法来完成。

// 生成 words 的所有排列

List<String> permutations = new ArrayList<>();
// 把数组转成集合    List<String> list = new ArrayList<>();    Collections.addAll(list, words);
// 生成所有排列    for (List<String> permutation : Collections2.permutations(list)) {        StringBuilder sb = new StringBuilder();        for (String word : permutation) {            sb.append(word);        }        permutations.add(sb.toString());    }
return permutations;}

比如说，我们有一个 words = ["foo","bar"]，那么我们可以生成所有的排列：

• foobar
• barfoo

当然了，这里也可以使用回溯算法来完成，代码如下：

class PermutationsGenerator {

// 生成所有排列的方法    public List<String> generatePermutations(String[] words) {        List<String> results = new ArrayList<>();        permute(words, 0, results);        return results;    }
// 辅助方法：递归地生成排列    private void permute(String[] array, int start, List<String> result) {        if (start >= array.length) {            // 将当前排列转换为字符串并添加到结果列表            result.add(String.join("", array));        } else {            for (int i = start; i < array.length; i++) {                swap(array, start, i); // 交换元素                permute(array, start + 1, result); // 递归地生成剩余元素的排列                swap(array, start, i); // 撤销交换            }        }    }
// 交换数组中的两个元素    private void swap(String[] array, int i, int j) {        String temp = array[i];        array[i] = array[j];        array[j] = temp;    }
public static void main(String[] args) {        PermutationsGenerator generator = new PermutationsGenerator();        String[] words = {"a", "b", "c"};        List<String> permutations = generator.generatePermutations(words);        System.out.println("排列组合: " + permutations);    }}

②、然后我们再来检查每个排列是否为 s 的子串。判断子串就比较简单了，直接使用 indexOf 方法就可以了。

当然了，一次 indexOf 是不够的，容易漏掉所有的情况，所以要使用 while 循环配合 indexOf 的重载方法 index = s.indexOf(permutation, index + 1)来完成。

public List findSubstring(String s, String[] words) {

List<Integer> result = new ArrayList<>();    // 生成所有 words 的排列    List<String> permutations = generatePermutations(words);    // 检查每个排列是否为 s 的子串    for (String permutation : permutations) {        int index = s.indexOf(permutation);        while (index != -1) {            // 如果找到，添加到结果列表中            if (!result.contains(index)) {                result.add(index);            }            // 继续查找下一个匹配的子串            index = s.indexOf(permutation, index + 1);        }    }
return result;}

不过，由于这个暴力解法的效率很低，我们就直接使用 ACM 的模式在 Intellij IDEA 中进行尝试了。这样方便帮助大家理解整个题解的过程。

class Main03001 {

    Solution03001 solution = new Solution03001();        String s = "barfoobarfoothefoobarman";        String[] words = {"foo", "bar"};        List<Integer> result = solution.findSubstring(s, words);        System.out.println(result);    }

}
class Solution03001 { public List findSubstring(String s, String[] words) { // 这是 LeetCode 的第 30 题 List result = new ArrayList<>(); // 生成所有 words 的排列 List permutations = generatePermutations(words); // 检查每个排列是否为 s 的子串 for (String permutation : permutations) { int index = s.indexOf(permutation); while (index != -1) { // 如果找到，添加到结果列表中 if (!result.contains(index)) { result.add(index); } // 继续查找下一个匹配的子串 index = s.indexOf(permutation, index + 1); } }
return result; }
// 生成 words 的所有排列 private List generatePermutations(String[] words) { List permutations = new ArrayList<>();
// 把数组转成集合 List list = new ArrayList<>(); Collections.addAll(list, words);
// 生成所有排列 for (List permutation : Collections2.permutations(list)) { StringBuilder sb = new StringBuilder(); for (String word : permutation) { sb.append(word); } permutations.add(sb.toString()); }
return permutations; }}

来看一下运行结果：

[3,15,0,6]

也是完全可以找出来的，不过，很遗憾，如果直接在 LeetCode 上用这种方法来完成的话，会超出时间限制。

但是，刷 LeetCode 其实并不只是为了刷题，更重要的是要学会分析问题，尤其是对于算法基础比较薄弱的球友，如果一上来就搞效率很高的解法，但看又看不懂，那就没有意义了。

分析 2

那我们接着来分析，看看能不能在暴力的基础上进一步优化，这次我们就不排列组合了，因为排列组合确实会比较花费时间，尤其是当 words 数组长度比较大的时候。

这次采用逆向思维。

第一步，我们直接在 s 中先截取一个长度为 words.length * words[0].length 的子串（words 数组中的字符串长度都相等），那么这个子串要么是串联子串，要么就不是，对吧？

第二步，再从这个子串中截取长度为 words[0].length 的子串，然后判断这个子串是否在 words 数组中，如果在的话，就继续截取下一个子串，直到截取完毕。

我们借助了两个哈希表来帮我们完成这项工作：

①、一个哈希表 cnt 用于记录 words 中每个单词应出现的次数，比如说：

• words = ["foo","bar"]，那么 cnt = {foo=1, bar=1}。
• words = ["foo","bar","foo"]，那么 cnt = {foo=2, bar=1}。

并且哈希表 cnt 的 key 还可以帮我们判断第二步中当前截取的子串是否在 words 数组中。

不在的话，就可以直接跳过这次循环了。

②、一个哈希表 com 用于记录当前考察的子串中各单词的出现次数

如果 com 中统计到的单词出现次数超过了它在 words 中应有的次数，那么说明当前子串不符合条件，立即跳出。

最后，如果 com 中统计到的和 cnt 完全一样，那么说明当前子串是符合条件的，将其起始索引添加到结果列表中。

我们来看一下完整的题解代码：

class Solution {

    List<Integer> res = new ArrayList<>();        if (s == null || words == null || words.length == 0) return res;
    // 单词的长度，假设所有单词长度相同        int wordLength = words[0].length();        // 所有单词串联起来的总长度        int allWordsLength = wordLength * words.length;        // 使用 cnt 哈希表来记录 words 中每个单词应出现的次数        Map<String, Integer> cnt = new HashMap<>();        for (String word : words) {            cnt.put(word, cnt.getOrDefault(word, 0) + 1);        }
    // 遍历字符串 s，考虑每一个可能的起始位置        for (int i = 0; i <= s.length() - allWordsLength; i++) {            // com 哈希表用于记录当前考察的子串中各单词的出现次数            Map<String, Integer> com = new HashMap<>();            // 提取从 i 开始长度为 allWordsLength 的子串            String temp = s.substring(i, i + allWordsLength);            boolean isValid = true; // 标记当前子串是否有效            // 再次遍历子串，每次移动一个单词的长度            for (int j = 0; j < temp.length(); j += wordLength) {                String t = temp.substring(j, j + wordLength);                // 如果 t 不在 cnt 中，说明当前子串不符合条件，立即跳出                if (!cnt.containsKey(t)) {                    isValid = false;                    break;                }                com.put(t, com.getOrDefault(t, 0) + 1);                // 如果当前单词 t 的出现次数超过了它在 words 中应有的次数，同样说明当前子串不符合条件                if (com.get(t) > cnt.get(t)) {                    isValid = false;                    break;                }            }            // 如果子串有效，将其起始索引添加到结果列表中            if (isValid && com.equals(cnt)) {                res.add(i);            }        }        return res;    }}

虽然题解效率并不乐观，但很好理解，对吧？

分析 3

我们来观察一下分析 2 中的过程：

对于每个长度为 6 的子串（words = ["foo","bar"]），我们都要检验一次，但是可以注意到，第一次和第四次，本质上就是去掉了一个bar加上一个the，第二次和第五次，本质上就是去掉了一个arf加上一个hef，第三次和第六次，本质上就是去掉了一个rfo加上了一个efo。

所以……我们可以考虑将他们分成单词长度组来看看他们的性质？

分组之后，每次只需要添加一个单词，再删去一个单词就可以得到了下一次的状态，这样子就不用费劲的重新构造这个字符串了。

每次添加一个单词和删去一个单词的代价也不高！

其实这样子就相当于设立了一个窗口，在字符串s上，以单词长度/每次的速度在移动，所以这也经常被称作滑动窗口。

我们在**003.无重复字符的最长子串 **中也曾详细讲过滑动窗口，其核心原理就在于利用滑动的窗口减少不必要的计算。

但其实思路和分析 2 的差不多，只是在实现上有所不同。

第一步，同样是遍历 s，准备一个滑动窗口，对窗口内的子串进行验证。

for (int i = 0; i }

因为是滑动窗口，所以第一个 for 循环只需要遍历 0 到 wordLen - 1 这个范围，见下图的三个红色框。如果 wordLen = 3，那么就是遍历 0、1、2 这三个位置，后续的处理交给滑动窗口。

![图片](https://clxhxhhr.top/uploads/weblog/erge/erge_lc_image_33.png)

第二步，在窗口内部，每次滑动的步长为一个单词的长度 j += wordLength;start += wordLength;，滑动窗口的宽度为所有单词的总长度 s.length() - windowLength。

for (int j = i; j // 处理一个窗口内的所有单词
// 左窗口右移一个单词的长度 start += wordLength; }}

如果窗口内的单词正好匹配 words 数组中的所有单词，则添加到结果中。

if (start == end) {

}

来看完整的题解：

class Solution {

    List<Integer> result = new ArrayList<>();        if (s == null || words == null || words.length == 0) return result;                // 创建一个HashMap来存储words数组中每个单词的出现次数        Map<String, Integer> wordCount = new HashMap<>();        for (String word : words) {            wordCount.put(word, wordCount.getOrDefault(word, 0) + 1);        }                // 单个单词的长度和窗口的长度（所有单词的总长度）        int wordLength = words[0].length();        int windowLength = words.length * wordLength;                // 遍历字符串s，每次增加的步长为一个单词的长度        for (int i = 0; i < wordLength; ++i) {            for (int j = i; j <= s.length() - windowLength; j += wordLength) {                // 用于记录当前窗口中单词的出现情况                Map<String, Integer> seenWords = new HashMap<>();                int start = j;                int end = j + windowLength;                                // 在窗口内部，每次也是按照单词的长度来切分和检查                while (start < end) {                    String currentWord = s.substring(start, start + wordLength);                    seenWords.put(currentWord, seenWords.getOrDefault(currentWord, 0) + 1);                                        // 如果当前单词不在words中，或者出现的次数超过了words中该单词的次数，则跳出循环                    if (!wordCount.containsKey(currentWord) || seenWords.get(currentWord) > wordCount.get(currentWord)) {                        break;                    }                    start += wordLength;                }                                // 如果窗口内的单词正好匹配words数组中的所有单词，则添加到结果中                if (start == end) {                    result.add(j);                }            }        }                return result;    }}

在这个题解中，同样借助了两个 HashMap 来帮助我们完成这项工作。

①、一个 HashMap wordCount 用于记录 words 数组中每个单词应出现的次数。

②、一个 HashMap seenWords 用于记录当前窗口中单词的出现情况。

也很好理解，大家看完代码注释就明白为什么了，来看一下题解效率：

显然比之前的效率提高了不少，对吧？

分析 4

我们再来看一种解法，这种解法是在分析 3 的基础上进一步优化的。

class Solution {

    List<Integer> res = new ArrayList<>();        if (s == null || words == null || s.length() == 0 || words.length == 0) return res;
    int wordLen = words[0].length(); // 单词的长度        int wordCount = words.length; // 单词的数量
    // 统计words中每个单词应该出现的次数        Map<String, Integer> wordMap = new HashMap<>();        for (String word : words) {            wordMap.put(word, wordMap.getOrDefault(word, 0) + 1);        }
    // 遍历所有的可能起始位置，0 到 wordLen - 1        for (int i = 0; i < wordLen; i++) {            int left = i; // 窗口左边界            int count = 0; // 窗口中符合条件的单词数量            Map<String, Integer> windowMap = new HashMap<>(); // 窗口中单词的计数
        // 移动窗口的右边界            for (int j = i; j <= s.length() - wordLen; j += wordLen) {                String word = s.substring(j, j + wordLen);
            // 如果word是有效的                if (wordMap.containsKey(word)) {                    windowMap.put(word, windowMap.getOrDefault(word, 0) + 1);                    count++;
                // 如果窗口中该单词的数量超过了应有的数量，需要调整窗口的左边界                    while (windowMap.get(word) > wordMap.get(word)) {                        String leftWord = s.substring(left, left + wordLen);                        windowMap.put(leftWord, windowMap.get(leftWord) - 1);                        count--;                        left += wordLen;                    }
                // 如果窗口中的单词数量正好等于words中的单词数量，记录起始位置                    if (count == wordCount) {                        res.add(left);                        // 移动左边界以寻找新的匹配                        String leftWord = s.substring(left, left + wordLen);                        windowMap.put(leftWord, windowMap.get(leftWord) - 1);                        count--;                        left += wordLen;                    }                } else {                    // 如果word不是有效的，则重置窗口                    windowMap.clear();                    count = 0;                    left = j + wordLen;                }            }        }        return res;    }}

分析 4 和分析 3 在解决问题的思路上都是一样，都是通过滑动窗口来遍历 s，然后在窗口内部，每次按照单词的长度来切分和检查。

但分析 4 采用了更细粒度的窗口移动策略，当遇到不匹配的单词时，它不是直接跳过整个窗口，而是逐个单词地调整窗口的左边界，直到窗口中的单词再次满足条件，或者窗口被完全重置。

这种策略的优势在于，它可以更快地找到下一个匹配的窗口，而不是直接跳过整个窗口。

所以效率也有了不少的提升，但实现比分析 3 复杂了不少。

总结

本题是一道 hard，但通过分析 1、分析 2、分析 3、分析 4 这么一套循序渐进的方式讲解下来，相信大家也都能够掌握了。

分析 1 非常直观，排列组合然后在 s 中查找，但效率不高。因为排列组合就需要花费很多时间。

分析 2 采用了逆向思维，先在 s 中截取一个长度为 words.length * words[0].length 的子串，然后再截取长度为 words[0].length 的子串，判断这个子串是否在 words 数组中，如果在的话，就继续截取下一个子串，直到截取完毕。这种方法效率就比分析 1 提高了一些。

分析 3 采用了滑动窗口的思想，也非常直观和容易掌握，效率也比分析 2 提高了不少。

分析 4 在分析 3 的基础上进一步优化，采用了更细粒度的窗口移动策略，效率提高了一大截，但代码量也多了不少。

好，我们来总结一下题解过程中所遇到的 Java 基础知识：

①、HashMap 的使用，包括 put、get、getOrDefault、clear 等方法的使用：HashMap 的深度解析

②、字符串的截取：Java 字符串截取

③、滑动窗口的使用：滑动窗口算法详解

力扣链接：https://leetcode.cn/problems/substring-with-concatenation-of-all-words/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100 天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

该题解目前只针对**二哥编程星球 **的球友开放，如果你也想一起打卡学习算法的话，扫下面的优惠券加入我们吧，星球目前 4500+ 人，定价 149 元，从当初的 99 元一路涨上来的，所以早就是优势，别再犹豫了。

（优惠券仅 300 张，数量有限）

一个人可以走得很快，但一群人才能走得更远。如果想去面中大厂的话，LeetCode 几乎是必刷的，二哥的 LeetCode 题解通俗易懂、图文并茂，理解给你举一反三的解题能力，冲鸭。

鲁迅曾说，人生就是一道道关，闯过去了，你就进阶了，闯不过去，你就原地踏步。年后这段时间不仅是春招、日常实习、社招都在同步进行，大家一定要抓紧时间。就算是离秋招，25 届也没有多少时间了，顶多 5 个月。每天一道二哥的 LeetCode 刷题笔记，继续进步。

技术派阅读地址：https://paicoding.com/column/7/ 30

• 语雀专栏地址+密码可通过星球置顶帖查看：https://t.zsxq.com/15rEo9Pdu

• 这道题可以说完全重写了，给出 4 道大家完全都能掌握的题解（ 暴力算法「2 种」+滑动窗口「2种」，写了几乎一天的时间，累死）。

• 增加代码注释，这样大家更容易看懂并掌握题解；

• 增加参考资料，这样大家可以从零基础直接开刷，减轻新手刷题的阻力；

• 增加手绘图，这样大家更容易理解解题思路；

• 增加 ACM 输入输出，这样大家可以在 Intellij IDEA 中进行调试；

• 增加题解模拟，这样大家可以根据题解模拟整个题解过程，看完会有一种“哦哦”恍然大悟的感觉；

• 图片上传至 OSS 并配合 CDN，提升大家在技术派网站中的阅读体感。

• 另外，这一版本会作为 PDF 的终稿随后在星球进行发布。

题意

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

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

例如，如果 words = ["ab","cd","ef"]， 那么 "abcdef"， "abefcd"，"cdabef"， "cdefab"，"efabcd"， 和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串，因为他不是任何 words 排列的连接。

返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。

难度

困难

示例

输入：s = "barfoothefoobarman", words = ["foo","bar"]

解释：因为 words.length == 2 同时 words[i].length == 3，连接的子字符串的长度必须为 6。子串 "barfoo" 开始位置是 0。它是 words 中以 ["bar","foo"] 顺序排列的连接。子串 "foobar" 开始位置是 9。它是 words 中以 ["foo","bar"] 顺序排列的连接。输出顺序无关紧要。返回 [9,0] 也是可以的。
输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]输出：[]解释：因为 words.length == 4 并且 words[i].length == 4，所以串联子串的长度必须为 16。s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。所以我们返回一个空数组。
输入：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

这道题，说实话，一开始看上去是有点懵逼的，因为描述了一大堆，有点抓不到重点。

以前版本的 LeetCode 描述中，例子也没有，我第一次看上去，确实有点摸不着头脑。

最新的 LeetCode 版本中加入了例子和解释，就清晰多了。

首先我们来搞清楚一个概念，什么是串联子串？

比如说一个字符串 s = abc，words = ["a","b","c"]。

words 所能组成的串联子串有：

• abc
• bac
• cab
• acb
• bca
• cba

然后，我们再来判断这些串联子串是否在 s 中，如果在的话，就返回它的起始位置。

那么显然，串联子串 abc 在 s 中，起始位置是 0。别的串联子串就不在。

那么很容易就能想到一种暴力解法，先排列组合出所有的串联子串，然后在 s 中查找这些子串，如果找到了，就记录它的起始位置。

①、我们使用 Guava 的 Collections2.permutations 方法来生成所有 words 的排列。借助 API 可以帮我们减轻排列组合的工作量，当然了，也可以直接使用回溯算法来完成。

// 生成 words 的所有排列

List<String> permutations = new ArrayList<>();
// 把数组转成集合    List<String> list = new ArrayList<>();    Collections.addAll(list, words);
// 生成所有排列    for (List<String> permutation : Collections2.permutations(list)) {        StringBuilder sb = new StringBuilder();        for (String word : permutation) {            sb.append(word);        }        permutations.add(sb.toString());    }
return permutations;}

比如说，我们有一个 words = ["foo","bar"]，那么我们可以生成所有的排列：

• foobar
• barfoo

当然了，这里也可以使用回溯算法来完成，代码如下：

class PermutationsGenerator {

// 生成所有排列的方法    public List<String> generatePermutations(String[] words) {        List<String> results = new ArrayList<>();        permute(words, 0, results);        return results;    }
// 辅助方法：递归地生成排列    private void permute(String[] array, int start, List<String> result) {        if (start >= array.length) {            // 将当前排列转换为字符串并添加到结果列表            result.add(String.join("", array));        } else {            for (int i = start; i < array.length; i++) {                swap(array, start, i); // 交换元素                permute(array, start + 1, result); // 递归地生成剩余元素的排列                swap(array, start, i); // 撤销交换            }        }    }
// 交换数组中的两个元素    private void swap(String[] array, int i, int j) {        String temp = array[i];        array[i] = array[j];        array[j] = temp;    }
public static void main(String[] args) {        PermutationsGenerator generator = new PermutationsGenerator();        String[] words = {"a", "b", "c"};        List<String> permutations = generator.generatePermutations(words);        System.out.println("排列组合: " + permutations);    }}

②、然后我们再来检查每个排列是否为 s 的子串。判断子串就比较简单了，直接使用 indexOf 方法就可以了。

当然了，一次 indexOf 是不够的，容易漏掉所有的情况，所以要使用 while 循环配合 indexOf 的重载方法 index = s.indexOf(permutation, index + 1)来完成。

public List findSubstring(String s, String[] words) {

List<Integer> result = new ArrayList<>();    // 生成所有 words 的排列    List<String> permutations = generatePermutations(words);    // 检查每个排列是否为 s 的子串    for (String permutation : permutations) {        int index = s.indexOf(permutation);        while (index != -1) {            // 如果找到，添加到结果列表中            if (!result.contains(index)) {                result.add(index);            }            // 继续查找下一个匹配的子串            index = s.indexOf(permutation, index + 1);        }    }
return result;}

不过，由于这个暴力解法的效率很低，我们就直接使用 ACM 的模式在 Intellij IDEA 中进行尝试了。这样方便帮助大家理解整个题解的过程。

class Main03001 {

    Solution03001 solution = new Solution03001();        String s = "barfoobarfoothefoobarman";        String[] words = {"foo", "bar"};        List<Integer> result = solution.findSubstring(s, words);        System.out.println(result);    }

}
class Solution03001 { public List findSubstring(String s, String[] words) { // 这是 LeetCode 的第 30 题 List result = new ArrayList<>(); // 生成所有 words 的排列 List permutations = generatePermutations(words); // 检查每个排列是否为 s 的子串 for (String permutation : permutations) { int index = s.indexOf(permutation); while (index != -1) { // 如果找到，添加到结果列表中 if (!result.contains(index)) { result.add(index); } // 继续查找下一个匹配的子串 index = s.indexOf(permutation, index + 1); } }
return result; }
// 生成 words 的所有排列 private List generatePermutations(String[] words) { List permutations = new ArrayList<>();
// 把数组转成集合 List list = new ArrayList<>(); Collections.addAll(list, words);
// 生成所有排列 for (List permutation : Collections2.permutations(list)) { StringBuilder sb = new StringBuilder(); for (String word : permutation) { sb.append(word); } permutations.add(sb.toString()); }
return permutations; }}

来看一下运行结果：

[3,15,0,6]

也是完全可以找出来的，不过，很遗憾，如果直接在 LeetCode 上用这种方法来完成的话，会超出时间限制。

但是，刷 LeetCode 其实并不只是为了刷题，更重要的是要学会分析问题，尤其是对于算法基础比较薄弱的球友，如果一上来就搞效率很高的解法，但看又看不懂，那就没有意义了。

分析 2

那我们接着来分析，看看能不能在暴力的基础上进一步优化，这次我们就不排列组合了，因为排列组合确实会比较花费时间，尤其是当 words 数组长度比较大的时候。

这次采用逆向思维。

第一步，我们直接在 s 中先截取一个长度为 words.length * words[0].length 的子串（words 数组中的字符串长度都相等），那么这个子串要么是串联子串，要么就不是，对吧？

第二步，再从这个子串中截取长度为 words[0].length 的子串，然后判断这个子串是否在 words 数组中，如果在的话，就继续截取下一个子串，直到截取完毕。

我们借助了两个哈希表来帮我们完成这项工作：

①、一个哈希表 cnt 用于记录 words 中每个单词应出现的次数，比如说：

• words = ["foo","bar"]，那么 cnt = {foo=1, bar=1}。
• words = ["foo","bar","foo"]，那么 cnt = {foo=2, bar=1}。

并且哈希表 cnt 的 key 还可以帮我们判断第二步中当前截取的子串是否在 words 数组中。

不在的话，就可以直接跳过这次循环了。

②、一个哈希表 com 用于记录当前考察的子串中各单词的出现次数

如果 com 中统计到的单词出现次数超过了它在 words 中应有的次数，那么说明当前子串不符合条件，立即跳出。

最后，如果 com 中统计到的和 cnt 完全一样，那么说明当前子串是符合条件的，将其起始索引添加到结果列表中。

我们来看一下完整的题解代码：

class Solution {

    List<Integer> res = new ArrayList<>();        if (s == null || words == null || words.length == 0) return res;
    // 单词的长度，假设所有单词长度相同        int wordLength = words[0].length();        // 所有单词串联起来的总长度        int allWordsLength = wordLength * words.length;        // 使用 cnt 哈希表来记录 words 中每个单词应出现的次数        Map<String, Integer> cnt = new HashMap<>();        for (String word : words) {            cnt.put(word, cnt.getOrDefault(word, 0) + 1);        }
    // 遍历字符串 s，考虑每一个可能的起始位置        for (int i = 0; i <= s.length() - allWordsLength; i++) {            // com 哈希表用于记录当前考察的子串中各单词的出现次数            Map<String, Integer> com = new HashMap<>();            // 提取从 i 开始长度为 allWordsLength 的子串            String temp = s.substring(i, i + allWordsLength);            boolean isValid = true; // 标记当前子串是否有效            // 再次遍历子串，每次移动一个单词的长度            for (int j = 0; j < temp.length(); j += wordLength) {                String t = temp.substring(j, j + wordLength);                // 如果 t 不在 cnt 中，说明当前子串不符合条件，立即跳出                if (!cnt.containsKey(t)) {                    isValid = false;                    break;                }                com.put(t, com.getOrDefault(t, 0) + 1);                // 如果当前单词 t 的出现次数超过了它在 words 中应有的次数，同样说明当前子串不符合条件                if (com.get(t) > cnt.get(t)) {                    isValid = false;                    break;                }            }            // 如果子串有效，将其起始索引添加到结果列表中            if (isValid && com.equals(cnt)) {                res.add(i);            }        }        return res;    }}

虽然题解效率并不乐观，但很好理解，对吧？

分析 3

我们来观察一下分析 2 中的过程：

对于每个长度为 6 的子串（words = ["foo","bar"]），我们都要检验一次，但是可以注意到，第一次和第四次，本质上就是去掉了一个bar加上一个the，第二次和第五次，本质上就是去掉了一个arf加上一个hef，第三次和第六次，本质上就是去掉了一个rfo加上了一个efo。

所以……我们可以考虑将他们分成单词长度组来看看他们的性质？

分组之后，每次只需要添加一个单词，再删去一个单词就可以得到了下一次的状态，这样子就不用费劲的重新构造这个字符串了。

每次添加一个单词和删去一个单词的代价也不高！

其实这样子就相当于设立了一个窗口，在字符串s上，以单词长度/每次的速度在移动，所以这也经常被称作滑动窗口。

我们在**003.无重复字符的最长子串 **中也曾详细讲过滑动窗口，其核心原理就在于利用滑动的窗口减少不必要的计算。

但其实思路和分析 2 的差不多，只是在实现上有所不同。

第一步，同样是遍历 s，准备一个滑动窗口，对窗口内的子串进行验证。

for (int i = 0; i }

因为是滑动窗口，所以第一个 for 循环只需要遍历 0 到 wordLen - 1 这个范围，见下图的三个红色框。如果 wordLen = 3，那么就是遍历 0、1、2 这三个位置，后续的处理交给滑动窗口。

![图片](https://clxhxhhr.top/uploads/weblog/erge/erge_lc_image_33.png)

第二步，在窗口内部，每次滑动的步长为一个单词的长度 j += wordLength;start += wordLength;，滑动窗口的宽度为所有单词的总长度 s.length() - windowLength。

for (int j = i; j // 处理一个窗口内的所有单词
// 左窗口右移一个单词的长度 start += wordLength; }}

如果窗口内的单词正好匹配 words 数组中的所有单词，则添加到结果中。

if (start == end) {

}

来看完整的题解：

class Solution {

    List<Integer> result = new ArrayList<>();        if (s == null || words == null || words.length == 0) return result;                // 创建一个HashMap来存储words数组中每个单词的出现次数        Map<String, Integer> wordCount = new HashMap<>();        for (String word : words) {            wordCount.put(word, wordCount.getOrDefault(word, 0) + 1);        }                // 单个单词的长度和窗口的长度（所有单词的总长度）        int wordLength = words[0].length();        int windowLength = words.length * wordLength;                // 遍历字符串s，每次增加的步长为一个单词的长度        for (int i = 0; i < wordLength; ++i) {            for (int j = i; j <= s.length() - windowLength; j += wordLength) {                // 用于记录当前窗口中单词的出现情况                Map<String, Integer> seenWords = new HashMap<>();                int start = j;                int end = j + windowLength;                                // 在窗口内部，每次也是按照单词的长度来切分和检查                while (start < end) {                    String currentWord = s.substring(start, start + wordLength);                    seenWords.put(currentWord, seenWords.getOrDefault(currentWord, 0) + 1);                                        // 如果当前单词不在words中，或者出现的次数超过了words中该单词的次数，则跳出循环                    if (!wordCount.containsKey(currentWord) || seenWords.get(currentWord) > wordCount.get(currentWord)) {                        break;                    }                    start += wordLength;                }                                // 如果窗口内的单词正好匹配words数组中的所有单词，则添加到结果中                if (start == end) {                    result.add(j);                }            }        }                return result;    }}

在这个题解中，同样借助了两个 HashMap 来帮助我们完成这项工作。

①、一个 HashMap wordCount 用于记录 words 数组中每个单词应出现的次数。

②、一个 HashMap seenWords 用于记录当前窗口中单词的出现情况。

也很好理解，大家看完代码注释就明白为什么了，来看一下题解效率：

显然比之前的效率提高了不少，对吧？

分析 4

我们再来看一种解法，这种解法是在分析 3 的基础上进一步优化的。

class Solution {

    List<Integer> res = new ArrayList<>();        if (s == null || words == null || s.length() == 0 || words.length == 0) return res;
    int wordLen = words[0].length(); // 单词的长度        int wordCount = words.length; // 单词的数量
    // 统计words中每个单词应该出现的次数        Map<String, Integer> wordMap = new HashMap<>();        for (String word : words) {            wordMap.put(word, wordMap.getOrDefault(word, 0) + 1);        }
    // 遍历所有的可能起始位置，0 到 wordLen - 1        for (int i = 0; i < wordLen; i++) {            int left = i; // 窗口左边界            int count = 0; // 窗口中符合条件的单词数量            Map<String, Integer> windowMap = new HashMap<>(); // 窗口中单词的计数
        // 移动窗口的右边界            for (int j = i; j <= s.length() - wordLen; j += wordLen) {                String word = s.substring(j, j + wordLen);
            // 如果word是有效的                if (wordMap.containsKey(word)) {                    windowMap.put(word, windowMap.getOrDefault(word, 0) + 1);                    count++;
                // 如果窗口中该单词的数量超过了应有的数量，需要调整窗口的左边界                    while (windowMap.get(word) > wordMap.get(word)) {                        String leftWord = s.substring(left, left + wordLen);                        windowMap.put(leftWord, windowMap.get(leftWord) - 1);                        count--;                        left += wordLen;                    }
                // 如果窗口中的单词数量正好等于words中的单词数量，记录起始位置                    if (count == wordCount) {                        res.add(left);                        // 移动左边界以寻找新的匹配                        String leftWord = s.substring(left, left + wordLen);                        windowMap.put(leftWord, windowMap.get(leftWord) - 1);                        count--;                        left += wordLen;                    }                } else {                    // 如果word不是有效的，则重置窗口                    windowMap.clear();                    count = 0;                    left = j + wordLen;                }            }        }        return res;    }}

分析 4 和分析 3 在解决问题的思路上都是一样，都是通过滑动窗口来遍历 s，然后在窗口内部，每次按照单词的长度来切分和检查。

但分析 4 采用了更细粒度的窗口移动策略，当遇到不匹配的单词时，它不是直接跳过整个窗口，而是逐个单词地调整窗口的左边界，直到窗口中的单词再次满足条件，或者窗口被完全重置。

这种策略的优势在于，它可以更快地找到下一个匹配的窗口，而不是直接跳过整个窗口。

所以效率也有了不少的提升，但实现比分析 3 复杂了不少。

总结

本题是一道 hard，但通过分析 1、分析 2、分析 3、分析 4 这么一套循序渐进的方式讲解下来，相信大家也都能够掌握了。

分析 1 非常直观，排列组合然后在 s 中查找，但效率不高。因为排列组合就需要花费很多时间。

分析 2 采用了逆向思维，先在 s 中截取一个长度为 words.length * words[0].length 的子串，然后再截取长度为 words[0].length 的子串，判断这个子串是否在 words 数组中，如果在的话，就继续截取下一个子串，直到截取完毕。这种方法效率就比分析 1 提高了一些。

分析 3 采用了滑动窗口的思想，也非常直观和容易掌握，效率也比分析 2 提高了不少。

分析 4 在分析 3 的基础上进一步优化，采用了更细粒度的窗口移动策略，效率提高了一大截，但代码量也多了不少。

好，我们来总结一下题解过程中所遇到的 Java 基础知识：

①、HashMap 的使用，包括 put、get、getOrDefault、clear 等方法的使用：HashMap 的深度解析

②、字符串的截取：Java 字符串截取

③、滑动窗口的使用：滑动窗口算法详解

力扣链接：https://leetcode.cn/problems/substring-with-concatenation-of-all-words/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100 天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

该题解目前只针对**二哥编程星球 **的球友开放，如果你也想一起打卡学习算法的话，扫下面的优惠券加入我们吧，星球目前 4500+ 人，定价 149 元，从当初的 99 元一路涨上来的，所以早就是优势，别再犹豫了。

（优惠券仅 300 张，数量有限）

一个人可以走得很快，但一群人才能走得更远。如果想去面中大厂的话，LeetCode 几乎是必刷的，二哥的 LeetCode 题解通俗易懂、图文并茂，理解给你举一反三的解题能力，冲鸭。

            知识星球
            
    
    
        
        扫码加入星球
        查看更多优质内容
    
    https://wx.zsxq.com/mweb/views/joingroup/join_group.html?group_id=15522885221412