1.题目描述
给定一个字符串 s 和一些 长度相同 的单词 words 。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
注意子串要与 words 中的单词完全匹配，中间不能有其他字符 ，但不需要考虑 words 中单词串联的顺序。
示例 1：
输入：s = "barfoothefoobarman", words = ["foo","bar"]
输出：[0,9]
解释：
从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。
输出的顺序不重要, [9,0] 也是有效答案。
示例 2：
输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
输出：[]
示例 3：
输入：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
输出：[6,9,12]
2.解题思路与代码
2.1 解题思路
这道题需要在字符串 s 中查找到给定 words 字符串数组，题目要求有几个特点：
- words 字符串数组中每个字符串长度一致
- words 字符串数组需要在 s 中连续并且只出现一次
根据这两个特点，可以使用一个固定长度的滑动窗口在 s 上进行遍历，因为 words 中字符串只出现一次，因此窗口长度为 words 数组中所有字符串的长度之和。首先使用一个 HashMap 统计 words 中每个单词出现的次数，然后窗口在 s 上滑动时每一次都统计窗口内单词出现的次数，如果单词在 words 中没有，或者出现单词数大于 words 中个数，退出当前窗口去下一个窗口继续判断。如果窗口内都满足，则将起始位置放入结果列表中返回。下面以示例 1 为例进行图解。
s 为 “barfoothefoobarman”，words 为 {"foo", "bar"}。在 words 中 foo 出现一次，bar 出现一次，一个字符串长度为 3 ，words 字符串长度总和为 6 ，因此窗口大小设定为 6。
从 s 第一位开始，窗口为 6 则在角标从 0 到 5 的字符进行判断。此时取 3 个字符得到 bar，bar 在 words 中，记录 bar 出现一次，并且角标从 4 开始继续判断。
此时再取 3 位字符得到 foo ，foo 在 words 中也存在，记录 foo 出现一次。此时这个窗口内组成的单词统计完毕，返回窗口左边界，并开始统计下一个窗口。
从新的窗口开始取单词得到 arf ，arf 并未出现在 words 中，结束当前窗口，统计下一个窗口
依次遍历每一个窗口，直到覆盖完字符串 s 为止
2.2 代码
class Solution {
public List<Integer> findSubstring(String s, String[] words) {
Map<String, Integer> wordsMap = new HashMap<>();
// 获取一个单词的长度
int wordLength = words[0].length();
// 计算 words 数组所有字符串长度作为窗口长度
int length = wordLength * words.length;
for (int i = 0; i < words.length; i++) {
// 统计 words 数组中每个字符串出现的次数
wordsMap.put(words[i], wordsMap.getOrDefault(words[i], 0) + 1);
}
List<Integer> ans = new ArrayList<>();
outerLoop:
for (int i = 0; i <= s.length() - length; i++) {
Map<String, Integer> windowMap = new HashMap<>();
int j = i;
while (j <= i + length - wordLength) {
// 获取窗口内单词
String word = s.substring(j, j + wordLength);
if (!wordsMap.containsKey(word)) {
// 如果单词不在 words 数组中，退出当前窗口
continue outerLoop;
}
if (windowMap.getOrDefault(word, 0) + 1 > wordsMap.get(word)) {
// 如果统计单词个数比 words 中该单词个数多，退出当前窗口
continue outerLoop;
}
// 统计窗口内单词出现次数
windowMap.put(word, windowMap.getOrDefault(word, 0) + 1);
// 从下一个单词开始统计
j += wordLength;
}
ans.add(i);
}
return ans;
}
}
2.3 测试结果
通过测试
3.总结
- 使用 HashMap 统计数组中以及窗口内的字符串出现的次数
- 使用固定大小窗口在字符串上进行遍历，并统计窗口内的单词
