串联所有单词的子串
给定一个字符串 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]
提示：
- 1 <= s.length <= 104
- s 由小写英文字母组成
- 1 <= words.length <= 5000
- 1 <= words[i].length <= 30
- words[i] 由小写英文字母组成
解题思路：
滑动窗口 + 哈希表
1、 一共用到两个 HashMap ：
- map 用于记录单词出现的次数，key 是 wards 中的每个元素值，value 是当前元素出现的次数, 在访问和修改 map 值的过程中我们可以使用
getOrDefault(w, 0)方法，设置一个默认值 0 . 规避 NPE 等简单的逻辑问题
- subMap 用于记录子串中（滑动窗口中）单词出现的次数，如果符合条件的一个周期之内如何找到符合条件的子字符串，或者找不到，将被重置。
来个图示:
2、wordLen 为单词的个数也就是 words.length， oneLen 也就是一个单词的长度也就是 words[0].length
3、遍历这个字符串，移动长度为 oneLen+ wordLen就是该 words 数组中所有字符长度的和。在滑动窗口中依次进行每个滑动窗口的比较。滑动坐标的最大值是 s.length - (oneLen * wordLen + 1) .
4、当这个窗口内一旦出现，不匹配 words 中的任意一个单词或者匹配的次数超过最大次数。那么本次滑动窗口不符合，直接 break进入下一个滑动窗口的匹配。
5、如果完全匹配上了，把这个滑动窗口的启始坐标加入结果中，最终走完所有的窗口将结果返回。
解题代码：
代码
解题代码如下：
class Solution { public List<Integer> findSubstring(String s, String[] words) { List<Integer> ans = new ArrayList<>(); // 判空 if (words == null || words.length == 0 || s == null || s.length() == 0) { return ans; } // 初始化 Map<String, Integer> map = new HashMap<>(); int oneLen = words[0].length(); int wordLen = words.length; int allLen = oneLen * wordLen; // 长度不够 if (s.length() < allLen) return ans; for (String w : words) { // 不存在子字符串 if (!s.contains(w)) return ans; map.put(w, map.getOrDefault(w, 0) + 1); } for (int i = 0; i < s.length() - allLen + 1; i++) { Map<String, Integer> subMap = new HashMap<>(); int idx = i; while (idx < i + allLen) { // 获取一个词 String curWord = s.substring(idx, idx + oneLen); // 如果不存在 || 已经存在且次数匹配足够 if (!map.containsKey(curWord) || Objects.equals(subMap.get(curWord), map.get(curWord))) { break; } subMap.put(curWord, subMap.getOrDefault(curWord, 0) + 1); idx += oneLen; } if (idx == i + allLen) { ans.add(i); } } return ans; } }
时间复杂度： 假设 s 的长度是 n，words 里有 m 个单词，那么时间复杂度就是 O（n * m）。
空间复杂度： 两个 HashMap，假设 words 里有 m 个单词，就是 O（m）。
总结
优化思考：
我们在每次逻辑的处理过程中是一个字母一个字母的移动，其实对于完全匹配的情况下，我们可以移动一个单词因为我们对符合条件的子串都匹配过了。还有就是当我们出现完全不匹配的单词的时候可以直接跳过，以及在超过次数的时候，只需要移除一个最前面重复的单词即可，最终优化时间复杂度可以达到 O(n) , 详细实现大家可以去在参考资料中查找详细实现。
第一个次认真的去梳理算法相关的文章，希望以后有时间能够和大家一起继续分享、学习。
