目录
问题描述
给定一个字符串 s 和一个字符串数组 words。words 中所有字符串长度相同。s 中的串联子串是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。我们需要返回所有串联子串在 s 中的开始索引。
示例
输入：
s = "barfoothefoobarman", words = ["foo","bar"]输出：[0,9]输入：
s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]输出：[]输入：
s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]输出：[6,9,12]
问题分析
这个问题可以通过滑动窗口和哈希表的方法来解决。我们需要检查字符串 s 中的每个可能的子串，看它是否由 words 数组中的所有单词组成。由于 words 中的单词长度相同，我们可以利用这个特性来优化我们的搜索。
算法设计
1. 初始化
- 创建一个空的
ArrayList来存储结果。 - 检查输入字符串
s和单词数组words是否为空，如果为空则直接返回空列表。 - 获取单词数组中每个单词的长度
oneLen。 - 使用
HashMap来存储每个单词出现的次数。
2. 滑动窗口
- 外层循环从
0到s.length() - oneLen * words.length，这是因为我们需要检查s中所有可能的子串。 - 对于每个起始位置
i，我们使用两个指针left和right来表示当前窗口的边界，并在窗口内维护一个哈希表tem来记录当前窗口中单词的出现次数。
3. 窗口扩展和收缩
- 内层循环通过移动
right指针来扩展窗口，直到窗口的大小超过字符串s的长度。 - 如果当前窗口中的字符串
str不在map中，清空tem并重置left指针，重新开始计数。 - 如果
str在map中，更新tem中str的计数。 - 如果
tem中str的计数超过了map中的计数，收缩窗口直到tem中str的计数不超过map中的计数。
4. 检查子串
- 如果
tem中的单词计数与words数组中的单词计数相等，则说明找到了一个符合条件的子串，将其起始位置left添加到结果列表中。 - 为了寻找下一个可能的子串，移除当前子串的第一个单词，并更新
left指针。
5. 返回结果
- 返回包含所有子串起始位置的列表。
过题图片
代码实现
java
class Solution {
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> res = new ArrayList<>();
int m = s.length(), n = words.length;
if (m == 0 || n == 0) return res;
int oneLen = words[0].length();
Map<String, Integer> map = new HashMap<>();
for (String word : words) {
map.put(word, map.getOrDefault(word, 0) + 1);
}
for (int i = 0; i <= m - oneLen * n; i++) {
Map<String, Integer> tem = new HashMap<>();
int count = 0;
for (int j = 0; j < n; j++) {
String str = s.substring(i + j * oneLen, i + (j + 1) * oneLen);
if (!map.containsKey(str) || tem.getOrDefault(str, 0) >= map.get(str)) {
i += oneLen * (j - count);
tem.clear();
count = 0;
} else {
tem.put(str, tem.getOrDefault(str, 0) + 1);
count++;
}
}
if (count == n) {
for (int k = 0; k < oneLen; k++) {
res.add(i);
i += oneLen;
for (int j = 0; j < n - 1; j++) {
String str = s.substring(i + j * oneLen, i + (j + 1) * oneLen);
tem.put(str, tem.getOrDefault(str, 0) - 1);
if (tem.get(str) == 0) {
i += oneLen * (n - 1 - count);
tem.clear();
count = 0;
break;
}
}
}
}
}
return res;
}
}题目地址
总结
这个问题考察了滑动窗口和哈希表的应用，通过维护一个当前窗口内单词的出现次数，我们可以有效地检查每个可能的子串是否满足条件。这种方法的时间复杂度为 O(n * m)，其中 n 是 words 数组的长度，m 是字符串 s 的长度。