滑动窗口(7)_串联所有单词的字串
目录
1. 题目链接:
OJ链接:串联所有单词的字串
2. 题目描述 :
给定一个字符串 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 <= 1041 <= words.length <= 50001 <= words[i].length <= 30words[i]和s由小写英文字母组成
3. 解法 :
强烈建议大家先去看一下找到字符串中所有字母异位词这道题,思路一样,只不过将字符换成了字符串.---找到字符串中所有字母异位词
题目解析:
这道题给了一个字符串s和一个字符数组words,words中所有字符串的长度相等
我们需要在s中找到包含 words 中所有字符串以任意顺序排列连接起来的子串。
比如说我们的words为["foor", "bar", "the"],那s中的字串可以是"foorbarthe",可以是"barfoorthe",但不能是"forobrateh"
也就是说,我们在判断时可以忽略words中字符串的顺序,但是words中的字符串一定要是完整的,我们是以words中的字符串判断是否s中含有words的串联字串
算法思路 :
如果我们把每一个单词看成一个一个字母,问题就变成了找到[字符串中所有的字母异位词].无非就是之前处理的对象是一个一个的字符,我们这里处理的对象是一个一个的单词.
就拿题目中的示例一来说:
我们定义left,right从起始位置开始,每次依次移动w[0].size()次,如果这个字符串在s哈希表中的个数<=w哈希表中的个数,我们的count++,当count == w哈希表的size时,我们将结果push_back到我们的vector中,然后下一次需要判断right - left + 1 > w[0].size() * w.size(),大于就是我们的区间超过了w的长度,需要更新维护一下我们的动态区间,也就是让left += w[0].size,但是这里要注意我们需要维护一下我们的count,当我们排出left在s的哈希表中的个数 <= w哈希表中该字符串的个数,我们就count--,循环结束后left++,再重复w[0].size()次上述过程
图解流程:
代码展示 :
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
vector<int> ret;
unordered_map<string, int> hash1;
for(auto ch : words) hash1[ch]++;
int n = words[0].size(), m = words.size();
for(int i = 0; i < n; i++)
{
unordered_map<string, int> hash2;
for(int left = i, right = i, count = 0; right + n <= s.size(); right += n)
{
string in = s.substr(right, n);
hash2[in]++;
if(hash1.count(in) && hash2[in] <= hash1[in]) count++;
if(right - left + 1 > n * m)
{
string out = s.substr(left, n);
if(hash1.count(out) && hash2[out] <= hash1[out]) count--;
hash2[out]--;
left += n;
}
if(count == m) ret.push_back(left);
}
}
return ret;
}
};
结果分析 :
这个 findSubstring 函数的主要目的是在字符串 s 中找到所有由给定的单词数组 words 中的单词组成的子串的起始索引。下面是对这个算法效率的分析。
时间复杂度
1.外层循环：for(int i = 0; i < n; i++) 迭代 n 次，n 是单词的长度。2.内层循环：for(int left = i, right = i, count = 0; right + n <= s.size(); right += n)，这个循环的复杂度是与字符串 s 的长度成正比。设 L 是 s 的长度，最坏情况下这个循环大约会执行 L / n 次（每次移动 n 个字符）。
3.操作复杂度：
substr 操作的复杂度是 O(n)，每次提取的子串都是长度为 n 的。
字典操作（unordered_map）的查找和插入平均时间复杂度是 O(1)，在最坏情况下是 O(n)。
因此，内层循环中关键操作的时间复杂度可以看作 O(L / n) * O(n) = O(L)。综合来看，外层循环和内层循环的总时间复杂度为：
O (n⋅( L / n ))=O(L)
空间复杂度
使用的额外空间主要是 unordered_map，用于存储单词的频率。假设 W 是 words 的长度，最坏情况下需要 O(W) 的空间。
另外，hash2 也需要 O(W) 的空间来存储当前窗口内的单词频率。
因此，总的空间复杂度为 O(W)。结论
综上所述，findSubstring 函数的时间复杂度是 O(L)，空间复杂度是 O(W)，是一个高效的算法，特别适合处理字符串匹配问题。对于较长的字符串和相对较短的单词列表，这种效率表现良好。
原文地址：https://blog.csdn.net/wer24_25/article/details/142363881
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！