网站开发与建设会计分录,开源免费企业网站源码,招商网站建设定做,中小企业网站制作模板前言#xff1a;这道题我做得有点崩溃#xff0c;前前后后做了很多次#xff0c;一直都卡在倒数第二个测试用例没有通过#xff0c;
本来是没打算发这道题的#xff0c;因为没怎么通过#xff0c;但想了一下#xff0c;我修改代码的过程还是蛮宝贵的#xff0c;所以就…前言这道题我做得有点崩溃前前后后做了很多次一直都卡在倒数第二个测试用例没有通过
本来是没打算发这道题的因为没怎么通过但想了一下我修改代码的过程还是蛮宝贵的所以就打算还是发出来启发一下你怎么修改代码所以这道题没什么参考价值我就随便写写咯
解题思路 1.获取信息 1给定一个字符串和字符串数组要求按任意顺序组合字符串数组中所有的字符串 再检验组合成的字符串是否是给定的那个字符串的子串 如果是就记录下子串的首字符在给定字符串的下标 2它给了例子可以结合例子理解一下 3那些首字符的下标们可以按任意顺序返回哦 2.分析题目 这道题让我想到了力扣第28题这道题的匹配字符串环节大概就是第28题第28题我使用了两种方法一种是滑动窗口法来匹配一种是KMP算法 这道题我就选用滑动窗口法来进行这一步骤一方面是简化这道题让它比较好理解一方面是给自己上上强度 这样我们就将这道题拆分成了两个小问题了其中一个小问题匹配子串我们已经知道怎么解决了另一个小问题就是该怎么获得字符串数组中字符串组合后形成的字符串了 具体获取方法我会放在下面的方法结合代码来帮助你理解 3.示例查验 示例1示例2和示例3你可以结合示例看一下自己获取的信息是否正确是否有遗漏 4.尝试编写代码 1递归配组合动态规划和滑动窗口来检验会超时 直接看代码吧跟28题的解法差不多只不过多了个递归而已
class Solution {
public:vectorint findSubstring(string s, vectorstring words) {vectorintres;string str;int sizewords.size();GetRes(res,str,size,0,s,words);return res;}
private:void GetRes(vectorintres,string str,int size,int now,strings,vectorstringwords){if(nowsize){int begin0,endstr.size()-1;while(ends.size()beginend){if(str[0]s[begin]str[str.size()-1]s[end])rever(s,str,begin,end,res);begin;end;}return;}for(int i0;isize;i){if(words[i])continue;string tempstr;tempwords[i];string UHwords[i];words[i];GetRes(res,temp,size,now1,s,words);words[i]UH;}}void rever(strings,string str,int begin,int end,vectorintres){int head0,tailstr.size()-1;int UHbegin;while(headtail){if(str[head]!s[begin]||str[tail]!s[end])return;begin;end--;head;tail--;}if(find(res.begin(),res.end(),UH)res.end()){res.push_back(UH);}}
}; 2尝试打算牺牲一下空间复杂度来拯救一下时间复杂度会超时 如方法名字所言就是这么个优化思路
class Solution {
public:vectorint findSubstring(string s, vectorstring words) {vectorintres;vectorstringtable;string str;int sizewords.size();GetRes(res,str,size,0,s,words,table);int bordertable.size();int UHs.size();for(int i0;iborder;i){int begin0,endtable[i].size()-1;while(endUHbeginend){if(s[begin]table[i][0]s[end]table[i][table[i].size()-1])rever(s,table[i],begin,end,res);begin;end;}}return res;}
private:void GetRes(vectorintres,string str,int size,int now,strings,vectorstringwords,vectorstringtable){if(nowsize){if(find(table.begin(),table.end(),str)table.end())table.push_back(str);return;}for(int i0;isize;i){if(words[i])continue;string tempstr;tempwords[i];string UHwords[i];words[i];GetRes(res,temp,size,now1,s,words,table);words[i]UH;}}void rever(strings,string str,int begin,int end,vectorintres){int head0,tailstr.size()-1;int UHbegin;while(headtail){if(str[head]!s[begin]||str[tail]!s[end])return;begin;end--;head;tail--;}res.push_back(UH);}
}; 3另辟蹊径法会超时 上面的方法我尽可能优化过了没办法只好推倒重来了
class Solution {
public:vectorint findSubstring(string s, vectorstring words) {vectorintres;int capwords[0].size();int sizewords.size()*cap;for(int i0;is.size();i){int endisize-1;if(ends.size()GetRes(s,i,end,cap,words))res.push_back(i);}return res;}
private:bool GetRes(strings,int begin,int end,int cap,vectorstringwords){while(beginend){string strs.substr(begin,cap);int i0;for(i;iwords.size();i){if(words[i]str){words[i];i-1;break;}}if(i!-1)return false;begincap;}return true;}
}; 4处理了明显不是起始位置的位置会超时
class Solution {
public:vectorint findSubstring(string s, vectorstring words) {unordered_mapchar,boolhead;unordered_mapstring,inthash;vectorintres;for(stringword:words){head[word[0]]true;hash[word];}int capwords[0].size();int roomcap*words.size();int borders.size();for(int i0;iborder;i){int endiroom-1;if(endborderhead.find(s[i])!head.end()Check(s,i,end,hash,cap))res.push_back(i);}return res;}
private:bool Check(strings,int begin,int end,unordered_mapstring,int hash,int cap){while(beginend){string strs.substr(begin,cap);hash[str];if(hash[str]0)return false;hash[str]--;begincap;}return true;}
}; 这是对上述方法的优化 5绞尽脑汁修改了一下超时 我尽力又再次修改了一下但还是不过
class Solution {
public:vectorint findSubstring(string s, vectorstring words) {unordered_mapchar,boolhead;unordered_mapstring,inthash;vectorintres;for(stringword:words){head[word[0]]true;hash[word];}int capwords[0].size();int roomcap*words.size();int borders.size();if(roomborder)return res;for(int i0;iborder-room;i){if(head.find(s[i])!head.end()Check(s,i,iroom-1,hash,cap))res.push_back(i);}return res;}
private:bool Check(strings,int begin,int end,unordered_mapstring,int hash,int cap){while(beginend){string strs.substr(begin,cap);hash[str];if(hash[str]0)return false;hash[str]--;begincap;}return true;}
}; 6推倒重来吧已经是我认为我能写出来的最极致的方法了但还是超时了 重新换了个思路发现还是不行现阶段我应该是写不出来了放到以后吧
class Solution {
public:vectorint findSubstring(string s, vectorstring words) {unordered_mapchar,boolhead;vectorintres;int capwords[0].size();int roomcap*words.size();int borders.size();if (roomborder)return res;for(stringword:words)head[word[0]]true;unordered_mapstring,intwordCount;for(stringword:words)wordCount[word];for(int i0;iborder-room;i) {if(!head.count(s[i]))continue;unordered_mapstring,inttemp;for(int ji;jiroom;jcap){string strs.substr(j,cap);if(!head.count(str[0]))break;temp[str];}if(tempwordCount)res.push_back(i);}return res;}
};这次的题解看看就行了毕竟我写的代码哪个都没通过还是有点丢人的你可以参考一下我这种优化优化不行就换思路的方法和不服输的精神坚持不懈的毅力嘛
等以后再重写这道题吧暂时放弃了
