#yyds干货盘点# LeetCode程序员面试金典：串联所有单词的子串

题目：

给出字符串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"] 连接顺序排列。

代码实现：

class Solution {    public List<Integer> findSubstring(String s, String[] words) {        List<Integer> res = new ArrayList<Integer>();        int m = words.length, n = words[0].length(), ls = s.length();        for (int i = 0; i < n; i++) {            if (i + m * n > ls) {                break;            }            Map<String, Integer> differ = new HashMap<String, Integer>();            for (int j = 0; j < m; j++) {                String word = s.substring(i + j * n, i + (j + 1) * n);                differ.put(word, differ.getOrDefault(word, 0) + 1);            }            for (String word : words) {                differ.put(word, differ.getOrDefault(word, 0) - 1);                if (differ.get(word) == 0) {                    differ.remove(word);                }            }            for (int start = i; start < ls - m * n + 1; start += n) {                if (start != i) {                    String word = s.substring(start + (m - 1) * n, start + m * n);                    differ.put(word, differ.getOrDefault(word, 0) + 1);                    if (differ.get(word) == 0) {                        differ.remove(word);                    }                    word = s.substring(start - n, start);                    differ.put(word, differ.getOrDefault(word, 0) - 1);                    if (differ.get(word) == 0) {                        differ.remove(word);                    }                }                if (differ.isEmpty()) {                    res.add(start);                }            }        }        return res;    }}