leetcode --- 30. 串联所有单词的子串[C++ 滑动窗口/双指针]
原题:30. 串联所有单词的子串 - 力扣(LeetCode)
题目解析:
本题在这道题的算法原理基础上进行思考会简单许多
leetcode --- 438. 找到字符串中所有字母异位词[C++/滑动窗口+哈希表]-CSDN博客
关键信息---words中的字符串长度都相等
要在s字符串中找到串联子串。将每一个words中的字符串看做一个字符
比如示例1中,foo看作a,bar看作b
那么s字符串就可以看成是 bacabd (the看作c,man看作d)
那么这道题就变成了和438一样的寻找异位词的问题。
但是这道题还有些不同的地方
比如barfoothefoobarman这个s字符串
除了从b开始的分割方式,还可能存在从第二个字符开始的分割方式,和第三个字符开始的分割方式,这几个分割方式中都可能出现符合题目要求的串联子串,只是示例1恰好没有。但是我们编写代码时要考虑到这个情况。
算法原理:
与438这道题不同的是:
1.这道题的哈希表要存的是字符串出现的频次;
2.此外,指针的移动方式也不同,每次移动的长度应该等于words中的字符串的长度;
3.还有一个不同就是题目解析中说的不同分割方式,这中不同在算法中的体现就是滑动窗口的执行次数。根据题目解析中的规律,当起始的字符跳过了一个words字符串的长度,那么就会和第一种情况(从第一个字符开始的分割方式)重复,所以滑动窗口的执行次数就是words字符串长度的大小。
先创建第一个哈希表hash1来保存words中字符出现的频次
再创建一个哈希表hash2用来保存窗口中字符出现的频次
滑动窗口四步走
1.进窗口 + 维护count
更新哈希表hash2,判断进窗口的字符串是否为有效字符串
有效则count++
2.判断
窗口长度大于words字符串总长度时出窗口
3.出窗口
判断出窗口的字符串是否为有效字符串
有效则count--
然后更新哈希表hash2,把出窗口的字符频次减掉
然后left指针右移
4.更新状态
当有效字符串个数等于words中的字符串个数
将left下标给返回值
以上步骤总共执行len次,len为words中一个字符串的长度
每一次执行的时候,left和right的起始位置要有相应变化
代码编写:
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
unordered_map<string,int>hash1; //保存words里所有单词出现的频次
for(auto &s : words)
{
hash1[s]++;
}
vector<int>ret;
int len = words[0].size(),m = words.size();
for(int i = 0;i<len;i++)//滑动窗口执行len次
{
unordered_map<string,int>hash2;//保存窗口内所有单词出现的频次
//right是其中一个字符串的起始位置,其长度要合法且符合要求
//所以循环的结束条件为right+len <= s.size()
//count为有效字符串个数
//注意left和right的起始位置要随滑动窗口执行次数变化而变化
for(int left = i,right = i,count = 0;right + len <= s.size(); right+=len)
{
//进窗口 + 维护count
string in = s.substr(right,len);
if(++hash2[in] <= hash1[in])
{
count++;
}
//判断
if(right - left + 1 > len*m)
{
string out = s.substr(left,len);
//出窗口
if(hash2[out]-- <= hash1[out])
{
count--;
}
left+=len;//出完窗口left要移动
}
//更新状态
if(count == m) //有效字符串个数等于words中字符串个数
{
ret.push_back(left);
}
}
}
return ret;
}
};
在时间上进一步优化
因为s字符串中可能出现words字符串中没有的字符,所以在进行比较的时候,hash1会先创建出一个空间再进行比较,这样就造成一定程度的时间消耗,所以在进行比较之前加个判断,hash1.count(in)判断这个字符串是否存在,如果不存在于words中,那就没有判断的必要,不影响有效字符串个数的大小。
优化地方在下方注释标出
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
unordered_map<string,int>hash1; //保存words里所有单词出现的频次
for(auto &s : words)
{
hash1[s]++;
}
vector<int>ret;
int len = words[0].size(),m = words.size();
for(int i = 0;i<len;i++)//滑动窗口执行len次
{
unordered_map<string,int>hash2;//保存窗口内所有单词出现的频次
//right是其中一个字符串的起始位置,其长度要合法且符合要求
//所以循环的结束条件为right+len <= s.size()
//count为有效字符串个数
//注意left和right的起始位置要随滑动窗口执行次数变化而变化
for(int left = i,right = i,count = 0;right + len <= s.size(); right+=len)
{
//进窗口 + 维护count
string in = s.substr(right,len);
if(hash1.count(in) && ++hash2[in] <= hash1[in]) //优化
{
count++;
}
//判断
if(right - left + 1 > len*m)
{
string out = s.substr(left,len);
//出窗口
if(hash1.count(out) && hash2[out]-- <= hash1[out]) //优化
{
count--;
}
left+=len;//出完窗口left要移动
}
//更新状态
if(count == m) //有效字符串个数等于words中字符串个数
{
ret.push_back(left);
}
}
}
return ret;
}
};
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!