JAVA解法
class Solution {
public List<Integer> findSubstring(String s, String[] words) {
// 定义一个存储符合要求的起始位置的 list
List<Integer> res = new ArrayList<>();
// 定义保存存储传进来的 words 中的所有相同长度的单词的 HashMap
Map<String, Integer> wordsMap = new HashMap<>();
if (s.length() == 0 || words.length == 0){
return res;
}
// 把所有目标单词存进去 wordsMap
for (String word: words) {
// 主串 s 中没有这个单词，直接返回空
if (s.indexOf(word) < 0){
return res;
}
// map 中保存每个单词，和它出现的次数
wordsMap.put(word, wordsMap.getOrDefault(word, 0) + 1);
}
// 每个单词的长度，和总长度
int oneLen = words[0].length(), wordsLen = oneLen * words.length;
// 主串 s 长度小于单词总和，返回空
if (wordsLen > s.length()){
return res;
}
/**
只讨论从 0，1，...， oneLen - 1 开始的子串情况，每次进行匹配的窗口
大小为 wordsLen，每次后移一个单词长度，由左右窗口维持当前窗口位置。
*/
for (int i = 0; i < oneLen; ++i) {
// 左右窗口
int left = i, right = i, count = 0;
// 统计每个符合要求的 word
Map<String, Integer> subMap = new HashMap<>();
// 右窗口不能超出主串长度
while (right + oneLen <= s.length()) {
// 得到一个单词
String word = s.substring(right, right + oneLen);
// 右窗口右移
right += oneLen;
// words[] 中没有这个单词，那么当前窗口肯定匹配失败，直接右移到这个单词后面
if (!wordsMap.containsKey(word)) {
left = right;
// 窗口内单词统计 map 清空，重新统计
subMap.clear();
// 符合要求的单词数清 0
count = 0;
} else {
// 统计当前子串中这个单词出现的次数
subMap.put(word, subMap.getOrDefault(word, 0) + 1);
++count;
/**
如果这个单词出现的次数大于 words[] 中它对应的次数，
又由于每次匹配和 words 长度相等的子串，
如 ["foo","bar","foo","the"] "| foobarfoobar| foothe"，
第二个bar虽然是 words[] 中的单词，但是次数超了，
那么右移一个单词长度后 "|barfoobarfoo|the"，
bar 还是不符合，所以直接从这个不符合的bar之后开始匹配，
也就是将这个不符合的 bar 和它之前的单词(串)全移出去
*/
while (subMap.getOrDefault(word, 0) > wordsMap.getOrDefault(word, 0)) {
// 从当前窗口字符统计 map 中删除从左窗口开始到数量超限的单词并且对应记录次数减一
String w = s.substring(left, left + oneLen);
subMap.put(w, subMap.getOrDefault(w, 0) - 1);
// 符合的单词数减一
--count;
// 左窗口位置右移
left += oneLen;
}
// 当前窗口字符串满足要求
if (count == words.length){
res.add(left);
}
}
}
}
return res;
}
}
题解分析
这道题用的是滑动窗口算法。首先，定义一个存储符合要求的起始位置的 list，定义保存存储传进来的 words 中的所有相同长度的单词的 HashMap，接着遍历传进来的 words 把所有目标单词存进去 wordsMap，map 中保存每个单词，和它出现的次数。获取每个单词的长度，和总长度。
最外层只讨论从 0，1，...， oneLen - 1 开始的子串情况，每次进行匹配的窗口，大小为 wordsLen，每次后移一个单词长度，由左右窗口维持当前窗口位置。定义左右窗口，统计每个符合要求的 word，并且右窗口不能超出主串长度。进入
while 循环，每得到一个单词，右窗口右移，若 words[] 中没有这个单词，那么当前窗口肯定匹配失败，直接右移到这个单词后面，则窗口内单词统计 map 清空，重新统计符合要求的单词数清 0。若 words[] 中有这个单词，则统计当前子串中这个单词出现的次数。
如果这个单词出现的次数大于 words[] 中它对应的次数，又由于每次匹配和 words 长度相等的子串，如 ["foo","bar","foo","the"] "| foobarfoobar| foothe"，第二个bar虽然是 words[] 中的单词，但是次数超了，那么右移一个单词长度后 "|barfoobarfoo|the"， bar 还是不符合，所以直接从这个不符合的bar之后开始匹配，也就是将这个不符合的 bar 和它之前的单词(串)全移出去。
若 subMap.getOrDefault(word, 0) > wordsMap.getOrDefault(word, 0) 即单词存在但次数超了，从当前窗口字符统计 map 中删除从左窗口开始到数量超限的单词并且对应记录次数减一，左窗口位置右移，并判断当前窗口字符串满足要求；若不存在次数超了的情况，则直接进入判断当前窗口字符串满足要求，若满足则 count++，若不满足则跳过判断继续到最近的 while 循环，直到整个 s 都匹配完则跳出 while 到最外层的 for 向右移动窗口，然后继续上述过程，直到最外层的 for 也遍历完整个 s 字符串，最终返回储存 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置的 res 数组。
leetcode原题： 30. 串联所有单词的子串
评论区