30. 串联所有单词的子串
给定一个字符串
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 <= 10(4)
1 <= words.length <= 5000
1 <= words[i].length <= 30
words[i]
和s
由小写英文字母组成
我们需要再s找一个子数组,这个子数组包含words的所有的元素。返回这个子数组的首索引。
注意到words里面的单词长度都是一样的。所以我们满足要求的所有子数组,都是按照单词的长度划分的。
我们将字符串看做一个整体,问题转化为在s子数组中找words的异位词。
利用map容器模拟hash表。hash1记录words中不同字符串对应的个数,hash2记录区间[left,right]中不同字符串对应的个数。
在s中划分字符串,有len=words[0].size()种划分情况。
对于每一种划分情况,我们只需要寻找符合要求的子数组即可。每一次遍历长度为len的字符串。
[left,right]区间,hash2记录区间[left,right]中不同字符串对应的个数,count记录区间内有效的字符个数,[left,right]长度不超过len*m。
因为[left,right]长度等于len*m的时候,就是对于left组合的一个解,对于后面的组合都不需要再考虑了,因为首索引都没有改变。
不断维护这个意义,我们每一次只需要判断count是否等于m,就知道[left,right] 是否符合条件。
当我们添加进right元素后,维护hash2和count。如果right-left+1>len*m,表示对于left的所有组合都考虑完毕了。left++。维护hash2和count。
此时[left,right]长度符合条件,hash2和count都维护成功,这就是一个可能的解,判断count==m,如果相等就是一个解。
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
vector<int> ret;
unordered_map<string, int> hash1;
for (auto& s : words)
hash1[s]++;
int len = words[0].size(), m = words.size();
for (int i = 0; i < len; i++) {
unordered_map<string, int> hash2;
for (int left = i, right = i, count = 0; right + len <= s.size();
right += len) {
string in = s.substr(right, len);
hash2[in]++;
if (hash1.count(in) && hash2[in] <= hash1[in])
count++;
if (right - left + 1 > m * len) {
string out = s.substr(left, len);
if (hash1.count(out) && hash2[out] <= hash1[out])
count--;
hash2[out]--;
left += len;
}
if (count == m)
ret.push_back(left);
}
}
return ret;
}
};
unordered_map<string, int> hash1;
定义了一个哈希表 hash1,用于存储 words 中每个单词的出现次数。
for (auto& s : words)
hash1[s]++;
遍历单词列表 words,更新哈希表 hash1,计算每个单词的出现次数。
int len = words[0].size(), m = words.size();
获取单词的长度 len(假设所有单词长度相同)和单词列表 words 的大小 m。
for (int i = 0; i < len; i++) {
由于单词有固定长度,所以使用多个滑动窗口,每个窗口的起始位置从 0 到 len-1。
unordered_map<string, int> hash2;
对于每个滑动窗口,定义一个哈希表 hash2,用于存储当前考察的窗口中每个单词的出现次数。
for (int left = i, right = i, count = 0; right + len <= s.size();
right += len) {
使用一个滑动窗口,窗口的左右边界分别由 left 和 right 表示,count 用来计数当前窗口内满足条件的单词数量,也就是有效字符的个数。窗口右边界 right 从 i 开始,每次移动一个单词的长度。
string in = s.substr(right, len);
获取当前右边界指向的单词 in。
hash2[in]++;
更新哈希表 hash2,计算当前窗口中每个单词的出现次数。
if (hash1.count(in) && hash2[in] <= hash1[in])
count++;
如果 in 存在于 hash1 中,并且 hash2[in] 的值不超过 hash1[in] 的值,则增加 count。
if (right - left + 1 > m * len) {
如果当前窗口的大小超过了所有单词串联后的长度,需要缩小窗口。
string out = s.substr(left, len);
获取当前左边界指向的单词 out。
if (hash1.count(out) && hash2[out] <= hash1[out])
count--;
如果 out 存在于 hash1 中,并且 hash2[out] 的值不超过 hash1[out] 的值,则减少 count。
hash2[out]--;
left += len;
减少 out 在哈希表 hash2 中的计数,并将左边界向右移动一个单词的长度。
if (count == m)
ret.push_back(left);
如果当前窗口内包含 words 中所有单词,则将当前左边界的索引添加到结果向量 ret 中。
时间复杂度和空间复杂度分析 时间复杂度:O(n * m * len),其中 n 是字符串 s 的长度,m 是单词列表 words 的大小,len 是单词的长度。每个窗口最多移动 n/len 次,每次移动需要 O(m * len) 的时间来处理窗口内的单词。
空间复杂度:O(m),主要是哈希表 hash1 和 hash2 的空间开销,它们存储了 words 中每个单词的出现次数。
76. 最小覆盖子串
给你一个字符串
s
、一个字符串t
。返回s
中涵盖t
所有字符的最小子串。如果s
中不存在涵盖t
所有字符的子串,则返回空字符串""
。注意:
对于
t
中重复字符,我们寻找的子字符串中该字符数量必须不少于t
中该字符数量。如果
s
中存在这样的子串,我们保证它是唯一的答案。示例 1:
输入:s = "ADOBECODEBANC", t = "ABC" 输出:"BANC" 解释:最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
示例 2:
输入:s = "a", t = "a" 输出:"a" 解释:整个字符串 s 是最小覆盖子串。
示例 3:
输入: s = "a", t = "aa" 输出: "" 解释: t 中两个字符 'a' 均应包含在 s 的子串中, 因此没有符合条件的子字符串,返回空字符串。
提示:
(m == s.length)
(n == t.length)
1 <= m, n <= 10(5)
s
和t
由英文字母组成进阶:你能设计一个在
o(m+n)
时间内解决此问题的算法吗?
滑动窗口(同向双指针)优化暴力枚举:
我们需要在[left,right]中判断是否包含t字符串,可以用hash1记录t字符串中不同字符的个数,用hash2记录[left,right]记录字符串中不同字符的个数,再用一个count记录[left,right]中有效的字符个数,我们仅需要判断count是否等于t.size(),就可以直接判断[left,right]中是否包含t字符串。
count记录有效字符的具体做法,我们考虑把right字符添加进区间中,添加right之前count记录是的[left,right-1]的有效字符个数,添加进right后,维护hash2,hash2[in]++。hash2维护之后,如果hash2[in]<=hash2[in],说明新加入进来的字符是有效字符,表示right字符有意义。
我们不断判断所有的子串区间,也就是所有的left和right的组合。找到符合条件的最小区间的长度。
[left,right]当添加进right后,count==m,此时对于left,与right+1,right+2...后面的组合都可以不用考虑了,因为子串的长度一定大于left与right的组合。也就是说对于left的所有组合我们都考虑完毕了。此时left++。
left++后,对于[left,right-1]这个区间的所有组合都不符合条件,所以跳过这个组合,直接从right开始匹配。
然后count==m,对于这个left的所有组合也考虑完毕。以此类推,直到count!=m为止。
left++的时候,需要注意维护hash2和count的意义。
class Solution {
public:
string minWindow(string s, string t) {
int n = s.size(), m = t.size();
if (n < m)
return "";
int hash1[128] = {0}, hash2[128] = {0};
for (auto ch : t)
hash1[ch]++;
int begin = -1, minlen = INT_MAX;
for (int left = 0, right = 0, count = 0; right < n; right++) {
char in = s[right];
hash2[in]++;
if (hash2[in] <= hash1[in])
count++;
while (count == m) {
if (right - left + 1 < minlen) {
minlen = right - left + 1;
begin = left;
}
char out = s[left];
if (hash2[out] <= hash1[out])
count--;
hash2[out]--;
left++;
}
}
if (begin == -1)
return "";
else
return s.substr(begin, minlen);
}
};
int n = s.size(), m = t.size();
获取字符串 s 和 t 的长度。
if (n < m)return "";
如果字符串 s 的长度小于字符串 t 的长度,返回空字符串,因为无法找到满足条件的窗口。
int hash1[128] = {0}, hash2[128] = {0};
定义两个哈希表 hash1 和 hash2,用于存储字符串 t 中每个字符的出现次数和当前考察的窗口中每个字符的出现次数。
for (auto ch : t)
hash1[ch]++;
遍历字符串 t,更新哈希表 hash1,计算 t 中每个字符的出现次数。
int begin = -1, minlen = INT_MAX;
初始化变量 begin 为-1,表示最小窗口的起始索引,初始化 minlen 为INT_MAX,表示最小窗口的长度。
for (int left = 0, right = 0, count = 0; right < n; right++) {
使用一个滑动窗口,窗口的左右边界分别由 left 和 right 表示,count 用来计数当前窗口内满足条件的字符数量,也就是有效字符数。窗口右边界 right 从0开始,遍历整个字符串 s。
char in = s[right];
获取当前右边界指向的字符 in。
hash2[in]++;
更新哈希表 hash2,计算当前窗口中每个字符的出现次数。
if (hash2[in] <= hash1[in])
count++;
如果当前字符 in 在窗口中的出现次数不超过它在 t 中的出现次数,则增加 count。
while (count == m) {
如果当前窗口内包含所有 t 中的字符,尝试缩小窗口以找到更小的窗口。
if (right - left + 1 < minlen) {
如果当前窗口大小小于已知的最小窗口大小,更新最小窗口大小和起始索引。
minlen = right - left + 1;
begin = left;
更新最小窗口的长度和起始索引。
char out = s[left];
获取当前左边界指向的字符 out。
if (hash2[out] <= hash1[out])
count--;
如果 out 在窗口中的出现次数不超过它在 t 中的出现次数,减少 count。
hash2[out]--;
left++;
减少字符 out 在哈希表 hash2 中的计数,并将左边界向右移动。 if (begin == -1)return "";elsereturn s.substr(begin, minlen);}
如果没有找到合适的窗口,返回空字符串。否则,返回从 begin 开始长度为 minlen 的子字符串。
时间复杂度和空间复杂度分析
时间复杂度:O(n),其中 n 是字符串 s 的长度。尽管有循环嵌套,但每个字符在 s 中只被访问两次(一次是当它进入窗口,一次是当它离开窗口),所以时间复杂度是线性的。
空间复杂度:O(1),因为 hash1 和 hash2 的大小固定为128(ASCII 字符集的大小),不依赖于输入数据的大小,因此可以认为是常数空间。
结尾
最后,感谢您阅读我的文章,希望这些内容能够对您有所启发和帮助。如果您有任何问题或想要分享您的观点,请随时在评论区留言。
同时,不要忘记订阅我的博客以获取更多有趣的内容。在未来的文章中,我将继续探讨这个话题的不同方面,为您呈现更多深度和见解。
谢谢您的支持,期待与您在下一篇文章中再次相遇!