30. Substring with Concatenation of All Words
30. Substring with Concatenation of All Words
题目
You are given a string s and an array of strings words. All the strings of words are of the same length.
A concatenated substring in s is a substring that contains all the strings of any permutation of words concatenated.
- For example, if
words = ["ab","cd","ef"], then"abcdef","abefcd","cdabef","cdefab","efabcd", and"efcdab"are all concatenated strings."acdbef"is not a concatenated substring because it is not the concatenation of any permutation ofwords.
Return the starting indices of all the concatenated substrings ins. You can return the answer in any order.
Example 1:
Input: s = "barfoothefoobarman", words = ["foo","bar"]
Output: [0,9]
Explanation: Since words.length == 2 and words[i].length == 3, the concatenated substring has to be of length 6.
The substring starting at 0 is "barfoo". It is the concatenation of ["bar","foo"] which is a permutation of words.
The substring starting at 9 is "foobar". It is the concatenation of ["foo","bar"] which is a permutation of words.
The output order does not matter. Returning [9,0] is fine too.
Example 2:
Input: s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
Output: []
Explanation: Since words.length == 4 and words[i].length == 4, the concatenated substring has to be of length 16.
There is no substring of length 16 in s that is equal to the concatenation of any permutation of words.
We return an empty array.
Example 3:
Input: s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
Output: [6,9,12]
Explanation: Since words.length == 3 and words[i].length == 3, the concatenated substring has to be of length 9.
The substring starting at 6 is "foobarthe". It is the concatenation of ["foo","bar","the"] which is a permutation of words.
The substring starting at 9 is "barthefoo". It is the concatenation of ["bar","the","foo"] which is a permutation of words.
The substring starting at 12 is "thefoobar". It is the concatenation of ["the","foo","bar"] which is a permutation of words.
Constraints:
1 <= s.length <= 10^41 <= words.length <= 50001 <= words[i].length <= 30sandwords[i]consist of lowercase English letters.
题目大意
给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。
- s 中的 串联子串 是指一个包含
words中所有字符串以任意顺序排列连接起来的子串。
例如，如果 words = ["ab","cd","ef"]， 那么 "abcdef"， "abefcd"，"cdabef"， "cdefab"，"efabcd"， 和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串，因为他不是任何 words 排列的连接。 返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。
解题思路
此题是 第 438 题 找到字符串中所有字母异位词 的进阶版。不同的是第 438 题的元素是字母，而此题的元素是单词，可以用类似的滑动窗口方法来解此题。
- 使用双指针中的左右指针，初始化
left = right = 0，把索引左闭右开区间[left, right)称为一个「窗口」； - 不断地增加
right指针扩大窗口[left, right)，直到窗口中的字符串符合要求（包含了words.length * words[0].length个字符）； - 停止增加
right，转而不断增加left指针缩小窗口[left, right)，直到窗口中的字符串不再符合要求； - 每次窗口中的字符串长度符合要求时，都要通过
isConcatenatedString函数，判断窗口中的字符串是否符合题目要求，并更新一轮结果； - 重复第 2 和第 3 步，直到
right到达字符串s2的尽头；
- 时间复杂度：
O(l×n)，其中l是输入s的长度，n是words中每个单词的长度。需要做n次滑动窗口，每次需要遍历一次s。 - 空间复杂度：
O(m×n)，其中m是words的单词数，n是words中每个单词的长度。每次滑动窗口时，需要用一个哈希表保存单词频次。
代码
/**
* @param {string} s
* @param {string[]} words
* @return {number[]}
*/
var findSubstring = function (s, words) {
let window = '',
need = {};
for (let i of words) {
need[i] = (need[i] || 0) + 1;
}
const len = words.length * words[0].length;
let left = 0,
right = 0,
// 记录结果
res = [];
while (right < s.length) {
// 进行窗口内数据的一系列更新
window += s[right];
right++;
// 判断左侧窗口是否要收缩
while (window.length > len) {
left++;
// 进行窗口内数据的一系列更新
window = window.substring(1, window.length);
}
// 当窗口符合条件时，把起始索引加入 res
if (isConcatenatedString(window, words, need)) {
res.push(left);
}
}
return res;
};
// 判断 str 是否为 words 的串联子串
var isConcatenatedString = function (str, words, need) {
let obj = {},
valid = 0;
const n = words[0].length,
m = words.length;
if (str.length !== m * n) return false;
for (let i = 0; i < m; i++) {
let word = str.slice(i * n, (i + 1) * n);
if (need[word]) {
obj[word] = (obj[word] || 0) + 1;
if (obj[word] == need[word]) {
valid += 1;
}
}
}
return valid == Object.keys(need).length;
};