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

题意

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

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

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

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

难度

困难

示例

输入：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] 也是可以的。

输入：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 的所有排列
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;
}

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

• foobar
• barfoo

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

class PermutationsGenerator {

    // 生成所有排列的方法
    public List generatePermutations(String[] words) {
        List results = new ArrayList<>();
        permute(words, 0, results);
        return results;
    }

    // 辅助方法：递归地生成排列
    private void permute(String[] array, int start, List 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[] wo...