题目描述（题目难度，困难）
给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。
示例 1：
输入：
s = "barfoothefoobarman",
words = ["foo","bar"]
输出：[0,9]
解释：
从索引 0 和 9 开始的子串分别是 "barfoor" 和 "foobar" 。
输出的顺序不重要, [9,0] 也是有效答案。
示例 2：
输入：
s = "wordgoodgoodgoodbestword",
words = ["word","good","best","word"]
输出：[]
题目求解
解法一，暴力法
把 words 数组中的所有单词放入 HashMap ，同时统计每个单词的出现次数。借助 HashMap 快速查找的特点，来匹配 s 字符串。整体的思路很简单明了，就是挨个匹配。
class Solution {
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> result = new ArrayList<>();
if(s.length() == 0 || words.length == 0) return result;
Map<String, Integer> countMap = new HashMap<>();
for(int i = 0; i < words.length; ++i){
countMap.put(words[i], countMap.getOrDefault(words[i], 0)+1);
}
int wordLen = words[0].length();
int wordsLen = words.length*wordLen;
for(int i = 0; i <= s.length()-wordsLen; ++i){
Map<String, Integer> workMap = new HashMap<>();
int j;
for(j = 0; j < words.length; ++j){
String word = s.substring(i+j*wordLen, i+(j+1)*wordLen);
workMap.put(word, workMap.getOrDefault(word, 0)+1);
if(workMap.get(word) > countMap.getOrDefault(word, 0)) break; // 匹配失败
}
if(j == words.length) result.add(i);
}
return result;
}
}
注意 String 的 substring 方法的范围参数是 substring(int beginIndex, int endIndex) 区间前闭后开，除此之外还有 public CharSequence subSequence(int beginIndex, int endIndex) 和 public int codePointCount(int beginIndex, int endIndex)，其余方法都用 起始位置和长度 表示。
暴力法每个 substring 会被取若干遍，最多取 words.length 遍。
解法二，滑动窗口
使用在 s 上的滑动窗口来匹配 words 数组，双指针 left，right 分别表示窗口的开始和结束。
指针移动的单位长度为 words 数组中单词的长度 wordLen。
每次取 s 上 right 到 right+wordLen 的一个新单词加入窗口。
如果这个单词不在 words 数组中（借助 HashMap 判断），说明这个窗口不合格，就将 right 置为 right+wordLen，left 置为 right，继续找。
如果这个单词在 words 数组中，但在窗口中的出现次数大于在 words 数组中的出现次数，说明这个窗口还是不合格，需要不断的将 left 加上 wordLen，即不断的删除窗口最左边的单词，直到这个单词在窗口中的出现次数与在 words 数组中的出现次数相等为止。
否则就表示当前窗口的所有单词都在 words 数组中，窗口没有任何问题，当窗口长度 right-left 正好为 words 数组中所有单词的长度和时，就表示匹配成功，将 left 加入结果集。
class Solution {
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> result = new ArrayList<>();
if(s.length() == 0 || words.length == 0) return result;
Map<String, Integer> countMap = new HashMap<>();
int wordLen = words[0].length();
int wordsLen = words.length*wordLen;
for(String word : words){
countMap.put(word, countMap.getOrDefault(word, 0)+1);
}
for(int i = 0; i < wordLen; ++i){ // 错位遍历，保证所有情况都遍历到
int left = i, right = i;
Map<String, Integer> workMap = new HashMap<>();
while(right+wordLen <= s.length()){
String rw = s.substring(right, right+wordLen);
right += wordLen;
if(!countMap.containsKey(rw)){ // 重置窗口
left = right;
workMap.clear();
}else{
workMap.put(rw, workMap.getOrDefault(rw, 0)+1);
while(workMap.get(rw) > countMap.get(rw)){ // 删除左边单词，使窗口符合要求
String lw = s.substring(left, left+wordLen);
workMap.put(lw, workMap.get(lw)-1);
left += wordLen;
}
if(right-left == wordsLen) result.add(left);
}
}
}
return result;
}
}
滑动窗口右指针右移取一遍 substring，左指针右移可能又取一遍，所以每个 substring 最多取两遍，但至少取一遍。
解法三，更优的解法
class Solution {
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> list = new ArrayList<>();
if (words.length == 0 || s.length() < words.length * words[0].length()) {
return list;
}
Map<String, Integer> map = new HashMap<>();
for (int i = 0; i < words.length; i++) {
map.put(words[i], map.getOrDefault(words[i], 0) + 1);
}
int listLen = words.length;
int wordLen = words[0].length();
// 从 0 到 wordLen-1 依次遍历，保证能遍历所有情况。
for (int i = 0; i < wordLen; i++) {
for (int j = i; j <= s.length() - wordLen * listLen; j += wordLen) {
Map<String, Integer> map2 = new HashMap<>();
// 从尾往头遍历，判断往后第 k 个 len 位置的子串是否在 map 中
for (int k = listLen - 1; k >= 0; k--) {
String temp = s.substring(j + k * wordLen, j + (k + 1) * wordLen);
int val = map2.getOrDefault(temp, 0) + 1;
// 如果从 j+k*wordLen, j 到 (k+1)*wordLen 位置的子串不在 map 中
// 代表可以从 j 到 j+(k+1)*wordLen 这一段都可以舍弃
// 这里只需把 j 移动 k*wordLen，剩余的一个 wordLen 在循环体中移动。
if (val > map.getOrDefault(temp, 0)) {
j += k * wordLen;
break;
}
// k 到 0 代表找到了符合的子串
if (k == 0) {
list.add(j);
} else {
map2.put(temp, val);
}
}
}
}
return list;
}
}
匹配时从后往前遍历，同样最多取两遍 substring，但最少是 0 遍。
网友评论