30. 串联所有单词的子串
给定一个字符串 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”] 顺序排列的连接。
提示：
1 <= s.length <= 104
1 <= words.length <= 5000
1 <= words[i].length <= 30
words[i] 和 s 由小写英文字母组成
- 朴素哈希表：由于每个单词长度相同，所以我们记录单词长度为 w，字符串 s 长度为 n，单词个数为 m，我们可以用一个哈希表 map 记录每个单词出现的次数。然后我们遍历 s，分割出一个个长度为 w*m 的子串 sub，将 sub 以 w 的长度为一组拆分成数个单词用另一个哈希表 cur 记录，如果 cur 与 map 相等就表示 sub 中的所有单词和个数都和 words 中的单词和个数相同，那就记录一个答案。如果 sub 中出现了不在 words 中的单词就直接结束外层当前循环进行剪纸。
public List<Integer> findSubstring(String s, String[] words) { List<Integer> res = new ArrayList<>(); Map<String,Integer> map = new HashMap<>(); for (String word : words) map.put(word, map.getOrDefault(word, 0) + 1); int n = s.length(), m = words.length, w = words[0].length(); out:for(int i = 0; i + m * w <= n; i++){ Map<String, Integer> cur = new HashMap<>(); String sub = s.substring(i, i + m * w); for(int j = 0; j < sub.length(); j += w){ String item = sub.substring(j, j + w); if(!map.containsKey(item))continue out; cur.merge(item, 1, Integer::sum); } if(cur.equals(map))res.add(i); } return res; }- 滑动窗口+哈希表：我们可以通过滑动窗口的方法，还是先用哈希表 map 记录 words 中每个单词的个数，然后开始滑动窗口。用哈希表 cur 记录当前窗口中的每个单词的个数，固定窗口长度为
m * w，每次滑动 w 长度，当窗口长度大于m * w就移除 cur 中记录的被移出窗口的单词，然后不断判断窗口 (相当于上面解法中的 sub) 是否和最开始记录的 map 一致。 - 比如 s 为 abcabc，words 为 [“abc”]，那么我们的窗口会为 abcabc -> abcabc，这两个窗口都和 words 一致所以返回 0, 3
- 但是我们要找的子串不一定正好是从头开始滑动窗口就能找到的，比如 xabcxx，从头开始滑动窗口只能得到 xabcxx -> xabcxx，所以根据下标对 w 的余数进行分类即可，即还需要尝试 xabcxx, xabcxx，再往后其实就是重复计算了，又会得到 xabcxx，所以是根据余数进行分类
public List<Integer> findSubstring(String s, String[] words) { List<Integer> res = new ArrayList<>(); Map<String,Integer> map = new HashMap<>(); // 依然用 map 记录 words 中的单词以及个数 for (String word : words) map.put(word, map.getOrDefault(word, 0) + 1); int n = s.length(), m = words.length, w = words[0].length(); // 根据对 w 的余数进行分类处理 for(int i = 0; i < w; i++){ // cur 记录每次窗口中的单词以及个数，开始滑动窗口 Map<String, Integer> cur = new HashMap<>(); for(int j = i + w; j <= n; j += w){ String word = s.substring(j - w, j); cur.merge(word, 1, Integer::sum); // 窗口大于 m * w 时需要缩小窗口，即需要移除窗口中最前面的一个单词 if(j - i > m * w){ String remove = s.substring(j - (m + 1) * w, j - m * w); if(cur.get(remove) == 1)cur.remove(remove); else cur.put(remove, cur.get(remove) - 1); } if(cur.equals(map))res.add(j - m * w); } } return res; }
