37-串联所有单词的子串

给定一个字符串 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 由小写英文字母组成

方法一：暴力枚举法

该方法通过遍历字符串 s 中所有可能的子串，将其按照 words 中单词的长度进行分割，然后检查分割后的单词是否与 words 中的单词完全匹配（不考虑顺序）。

function findSubstring(s: string, words: string[]): number[] {const result: number[] = [];if (s.length === 0 || words.length === 0) {return result;}const wordLength = words[0].length;const totalLength = wordLength * words.length;const wordCount = new Map<string, number>();for (const word of words) {wordCount.set(word, (wordCount.get(word) || 0) + 1);}for (let i = 0; i <= s.length - totalLength; i++) {const currentCount = new Map<string, number>();let j = 0;while (j < totalLength) {const word = s.slice(i + j, i + j + wordLength);if (!wordCount.has(word)) {break;}currentCount.set(word, (currentCount.get(word) || 0) + 1);if (currentCount.get(word)! > wordCount.get(word)!) {break;}j += wordLength;}if (j === totalLength) {result.push(i);}}return result;
}

复杂度分析

• 时间复杂度：(O(n * m * k))，其中 n 是字符串 s 的长度，m 是 words 数组的长度，k 是 words 中每个单词的长度。因为需要遍历 s 中所有可能的子串，对于每个子串，需要检查其中的单词是否与 words 匹配。
• 空间复杂度：(O(m))，主要用于存储 wordCount 和 currentCount 两个哈希表，其中 m 是 words 数组的长度。

方法二：滑动窗口法

使用滑动窗口来优化暴力枚举的过程，通过移动窗口来检查不同位置的子串是否满足条件。

function findSubstring(s: string, words: string[]): number[] {const result: number[] = [];if (s.length === 0 || words.length === 0) {return result;}const wordLength = words[0].length;const totalLength = wordLength * words.length;const wordCount = new Map<string, number>();for (const word of words) {wordCount.set(word, (wordCount.get(word) || 0) + 1);}for (let start = 0; start < wordLength; start++) {let left = start;let right = start;const currentCount = new Map<string, number>();let matchCount = 0;while (right + wordLength <= s.length) {const word = s.slice(right, right + wordLength);right += wordLength;if (wordCount.has(word)) {currentCount.set(word, (currentCount.get(word) || 0) + 1);if (currentCount.get(word)! <= wordCount.get(word)!) {matchCount++;}while (currentCount.get(word)! > wordCount.get(word)!) {const leftWord = s.slice(left, left + wordLength);currentCount.set(leftWord, currentCount.get(leftWord)! - 1);if (currentCount.get(leftWord)! < wordCount.get(leftWord)!) {matchCount--;}left += wordLength;}if (matchCount === words.length) {result.push(left);const leftWord = s.slice(left, left + wordLength);currentCount.set(leftWord, currentCount.get(leftWord)! - 1);matchCount--;left += wordLength;}} else {currentCount.clear();matchCount = 0;left = right;}}}return result;
}

复杂度分析

• 时间复杂度：(O(n * k))，其中 n 是字符串 s 的长度，k 是 words 中每个单词的长度。因为对于每个起始偏移量，只需要遍历一次 s。
• 空间复杂度：(O(m))，主要用于存储 wordCount 和 currentCount 两个哈希表，其中 m 是 words 数组的长度。

方法三：递归回溯法

通过递归生成 words 所有可能的排列，然后在字符串 s 中查找这些排列对应的子串。

function findSubstring(s: string, words: string[]): number[] {const result: number[] = [];if (s.length === 0 || words.length === 0) {return result;}const wordLength = words[0].length;const totalLength = wordLength * words.length;const permutations = getPermutations(words);for (const permutation of permutations) {const target = permutation.join('');let index = s.indexOf(target);while (index!== -1) {result.push(index);index = s.indexOf(target, index + 1);}}return result;
}function getPermutations(arr: string[]): string[][] {const result: string[][] = [];const backtrack = (path: string[], used: boolean[]) => {if (path.length === arr.length) {result.push([...path]);return;}for (let i = 0; i < arr.length; i++) {if (used[i]) continue;path.push(arr[i]);used[i] = true;backtrack(path, used);path.pop();used[i] = false;}};backtrack([], new Array(arr.length).fill(false));return result;
}

复杂度分析

• 时间复杂度：(O(m! * n))，其中 m 是 words 数组的长度，n 是字符串 s 的长度。因为需要生成 words 的所有排列，排列的数量为 (m!)，对于每个排列，需要在 s 中查找其出现的位置。
• 空间复杂度：(O(m! * m))，主要用于存储 words 的所有排列，排列的数量为(m!)，每个排列包含 m 个单词。

你可以使用以下方式测试这些函数：

const s1 = "barfoothefoobarman";
const words1 = ["foo", "bar"];
console.log(findSubstring(s1, words1));const s2 = "wordgoodgoodgoodbestword";
const words2 = ["word", "good", "best", "word"];
console.log(findSubstring(s2, words2));const s3 = "barfoofoobarthefoobarman";
const words3 = ["bar", "foo", "the"];
console.log(findSubstring(s3, words3));

综上所述，滑动窗口法是解决该问题的最优方法，时间复杂度相对较低。