题目描述
给定一个字符串 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"] 顺序排列的连接。
提示：
- words[i] 和 s 由小写英文字母组成
题目解析
由题目可知
words数组中每一个单词的长度都相同，结合数组长度可以计算出 “串联子串” 的长度
- 记
len(串联子串) = n(数组长度) * singleLen(单个字符串长度)
- 那么需要从给定的字符串
s中寻找符合条件的 “串联子串” 的开始索引 - 比较容易想到通过长度为
len的窗口去遍历 字符串s - 然后接下来问题变成：如何验证 当前遍历到的字符串 是不是 一个符合条件的“串联子串”
- 一个比较直接的办法
- 处理字符串，提取每一个单词并放到map集合中去
- 然后把
words数组的单词也放到 map 集合中去 - 对比两个map是否相同
show code
class Solution {
public List<Integer> findSubstring(String s, String[] words) {
int n = words.length;
int singleWordLen = words[0].length();
// 总长度
int len = n * singleWordLen;
// 结果集合
List<Integer> ans = new ArrayList<>();
if(len > s.length()) {
return ans;
}
// 总长度作为滑动窗口去遍历字符串 s
// 然后验证 窗口内的子串 是否是 words 数组其中一种可能的排列.
// 把 words 转存成 map
Map<String, Integer> wMap = new HashMap<>();
for (String word : words) {
wMap.put(word, wMap.getOrDefault(word, 0) + 1);
}
// 遍历 s .
for (int i = 0; i <= s.length() - len; i++) {
// 滑动窗口 [i, i + len]
if(check(s.substring(i, i + len), wMap, singleWordLen)) {
ans.add(i);
}
}
return ans;
}
private boolean check(String s, Map<String, Integer> wMap, int len) {
// 现在问题变成了，验证 字符串 s 是否是 words 数组的全排列可能之一.
// 首先可以确定的事情是 ： s 的长度和 words 中所有子串的长度相同.
// 需要找到一个比较好的验证方法.
// 如何验证？
// 是不是可以统计 words 中所有单词出现的次数？然后双重遍历
Map<String, Integer> map = new HashMap<>();
// 解析 字符串 s 转存成 map
int n = s.length();
for (int i = 0; i < n; i += len) {
String word = s.substring(i, i + len);
map.put(word, map.getOrDefault(word, 0) + 1);
}
for (Map.Entry<String, Integer> entry : wMap.entrySet()) {
if(map.containsKey(entry.getKey()) && Objects.equals(entry.getValue(), map.get(entry.getKey()))) {
continue;
} else {
return false;
}
}
return true;
}
}