30. 串联所有单词的子串
30. 串联所有单词的子串
🔴 🔖 哈希表
字符串
滑动窗口
🔗 力扣
LeetCode
题目
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^4
1 <= words.length <= 5000
1 <= words[i].length <= 30
s
andwords[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;
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 |
---|---|---|---|---|
76 | 最小覆盖子串 | [✓] | 哈希表 字符串 滑动窗口 |