30. 串联所有单词的子串
1. 题目
给定一个字符串 s
和一个字符串数组 words
。 words
中所有字符串 长度相同。
s
中的 串联子串 是指一个包含 words
中所有字符串以任意顺序排列连接起来的子串。
- 例如,如果
words = ["ab","cd","ef"]
, 那么"abcdef"
,"abefcd"
,"cdabef"
,"cdefab"
,"efabcd"
, 和"efcdab"
都是串联子串。"acdbef"
不是串联子串,因为他不是任何words
排列的连接。
返回所有串联子串在 s
中的开始索引。你可以以 任意顺序 返回答案。
示例 1:
1 | 输入:s = "barfoothefoobarman", words = ["foo","bar"] |
示例 2:
1 | 输入:s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"] |
示例 3:
1 | 输入:s = "barfoofoobarthefoobarman", words = ["bar","foo","the"] |
提示:
1 <= s.length <= 104
1 <= words.length <= 5000
1 <= words[i].length <= 30
words[i]
和s
由小写英文字母组成
2. 思路
整体利用滑动窗口的做法,配合着哈希表,对固定区间范围内的字符串进行一一比对
初始化前缀哈希表
preMap
变量,记录的是首个字符对应的单词集合初始化计数哈希表
countMap
变量,记录的是每个单词的数量初始化
length
变量用于记录words
数组中所有单词加起来的总长度,用于定义滑动窗口的大小,因为题目要求需要包含所有的单词初始化左指针
l
与右指针r
,每次判断滑动窗口范围内的字符是否能够包含所有的单词- 如果能够包含,则记录在结果集
result
当中
- 如果能够包含,则记录在结果集
每次检查完窗口范围内的匹配结果后,左指针
l
与右指针r
同时向右前进一格,如下图所示当检查滑动窗口内的字符是否能够匹配所有的单词时,可以用到前缀哈希表
preMap
找到对应滑动窗口内的单词集合- 如果无法在前缀哈希表
preMap
当中找到对应的单词集合,则表示窗口范围内的子串肯定无法串联所有的单词,此时返回匹配失败 - 如果能够在前缀哈希表
preMap
当中找到对应的单词集合,则继续判断遍历每个单词是否能够匹配到子串中 - 最终检查结果需要确保所有的单词都使用,过程中需要保证每个单词只能使用对应出现的次数
- 如果无法在前缀哈希表
3. 代码
以下代码还有一个优化点,即是使用计数不需要每次都重新开始
1 | class Solution { |
4. 复杂度
- 时间复杂度:
O(n)
- 空间复杂度:
O(n)