LeetCode30：串联所有单词的子串
原题地址：. - 力扣（LeetCode）
题目描述
给定一个字符串
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"] 顺序排列的连接提示：
1 <= s.length <= 1041 <= words.length <= 50001 <= words[i].length <= 30words[i]和s由小写英文字母组成
实现思路
滑动窗口： 我们从字符串
s的每个位置开始，尝试以每个位置为起点，滑动窗口逐步尝试匹配由给定单词数组中的单词拼接而成的子串。使用哈希表进行匹配： 使用一个哈希表
differ来存储当前窗口内每个单词的出现次数。我们通过不断地滑动窗口来更新这个哈希表。如果哈希表为空，表示当前窗口内的单词完全匹配了数组中的单词。优化滑动窗口： 在每一步滑动时，我们通过更新哈希表来移除旧单词并加入新单词，以保持窗口内的单词数量与目标单词数组一致。
终止条件： 如果滑动窗口内的所有单词匹配成功，即
differ哈希表为空，则将当前起始位置加入结果列表中。
源码实现
class Solution {
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> res = new ArrayList<Integer>(); // 存储结果的列表
int m = words.length, n = words[0].length(), ls = s.length();
// 遍历从 0 到 n 的每个可能的起点
for (int i = 0; i < n; i++) {
if (i + m * n > ls) { // 如果剩余的字符长度不够拼接所有单词，则跳过
break;
}
// 使用 HashMap 来记录每个单词的计数
Map<String, Integer> differ = new HashMap<String, Integer>();
// 初始窗口，提取从当前位置开始的 m 个单词
for (int j = 0; j < m; j++) {
String word = s.substring(i + j * n, i + (j + 1) * n); // 截取一个单词
differ.put(word, differ.getOrDefault(word, 0) + 1); // 更新计数
}
// 根据 words 数组中的单词，减少 differ 中对应单词的计数
for (String word : words) {
differ.put(word, differ.getOrDefault(word, 0) - 1);
if (differ.get(word) == 0) {
differ.remove(word); // 如果计数为 0，移除该单词
}
}
// 现在使用滑动窗口来检查每个子串
for (int start = i; start < ls - m * n + 1; start += n) { // 从当前起点开始，每次滑动 n 个字符
if (start != i) { // 如果不是初始起点
// 先移除滑动窗口左边的单词
String word = s.substring(start + (m - 1) * n, start + m * n);
differ.put(word, differ.getOrDefault(word, 0) + 1);
if (differ.get(word) == 0) {
differ.remove(word);
}
// 再添加新滑入窗口的单词
word = s.substring(start - n, start);
differ.put(word, differ.getOrDefault(word, 0) - 1);
if (differ.get(word) == 0) {
differ.remove(word);
}
}
// 如果哈希表为空，表示匹配成功
if (differ.isEmpty()) {
res.add(start); // 添加当前子串的起始位置到结果中
}
}
}
return res; // 返回所有匹配子串的起始位置
}
}
复杂度分析
时间复杂度：
- 外层循环：
for (int i = 0; i < n; i++)，最多执行n次，其中n是words[0]的长度。- 内层循环：
for (int start = i; start < ls - m * n + 1; start += n)，最多执行O((ls - m * n) / n)次，其中ls是字符串s的长度，m是words数组中的单词个数。- 在每一次内层循环中，我们需要通过哈希表进行单词的插入、删除和查找，这些操作的时间复杂度为
O(1)。- 因此，总的时间复杂度为
O(n * (ls - m * n) / n)，即O(m * n * ls)。空间复杂度：
- 我们使用了一个哈希表
differ来存储每个单词的出现次数，最坏情况下，哈希表的空间复杂度为O(m)，因为最多有m个单词。- 此外，结果列表
res存储所有匹配子串的起始位置，最坏情况下会有O(ls / (m * n))个匹配结果。- 因此，空间复杂度为
O(m + ls / (m * n))，但可以简化为O(m)。