鲁迅曾说，人生就是一道道关，闯过去了，你就进阶了，闯不过去，你就原地踏步。年后这段时间不仅是春招、日常实习、社招都在同步进行，大家一定要抓紧时间。就算是离秋招，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<String> generatePermutations(String[] 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<Integer> findSubstring(String s, String[] words) {
// 这是 LeetCode 的第 30 题
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 {
public static void main(String[] args) {
Solution03001 solution = new Solution03001();
String s = "barfoobarfoothefoobarma
1人已点赞
热门评论
1 条评论
回复