LeetCode--30.串联所有单词的子串

前言：这道题我做得有点崩溃，前前后后做了很多次，一直都卡在倒数第二个测试用例没有通过，

本来是没打算发这道题的，因为没怎么通过，但想了一下，我修改代码的过程还是蛮宝贵的，所以就打算还是发出来启发一下你怎么修改代码，所以，这道题没什么参考价值，我就随便写写咯

解题思路：

        1.获取信息：

                （1）给定一个字符串和字符串数组，要求按任意顺序组合字符串数组中所有的字符串

                         再检验组合成的字符串是否是给定的那个字符串的子串

                         如果是，就记录下子串的首字符在给定字符串的下标

                （2）它给了例子，可以结合例子理解一下

                （3）那些首字符的下标们可以按任意顺序返回哦

        2.分析题目：

                这道题让我想到了力扣第28题，这道题的匹配字符串环节大概就是第28题，第28题我使用了两种方法，一种是滑动窗口法来匹配，一种是KMP算法

                这道题我就选用滑动窗口法来进行这一步骤，一方面是简化这道题，让它比较好理解，一方面是给自己上上强度

                这样我们就将这道题拆分成了两个小问题了，其中一个小问题，匹配子串，我们已经知道怎么解决了，另一个小问题，就是该怎么获得字符串数组中字符串组合后形成的字符串了

                具体获取方法，我会放在下面的方法结合代码来帮助你理解

        3.示例查验：

                示例1，示例2和示例3：你可以结合示例看一下自己获取的信息是否正确，是否有遗漏

        4.尝试编写代码：

                （1）递归配组合，动态规划和滑动窗口来检验（会超时）

                        直接看代码吧，跟28题的解法差不多，只不过多了个递归而已

class Solution {
public:vector<int> findSubstring(string s, vector<string>& words) {vector<int>res;string str;int size=words.size();GetRes(res,str,size,0,s,words);return res;}
private:void GetRes(vector<int>&res,string str,int size,int now,string&s,vector<string>words){if(now==size){int begin=0,end=str.size()-1;while(end<s.size()&&begin<=end){if(str[0]==s[begin]&&str[str.size()-1]==s[end])rever(s,str,begin,end,res);begin++;end++;}return;}for(int i=0;i<size;i++){if(words[i]=="")continue;string temp=str;temp+=words[i];string UH=words[i];words[i]="";GetRes(res,temp,size,now+1,s,words);words[i]=UH;}}void rever(string&s,string str,int begin,int end,vector<int>&res){int head=0,tail=str.size()-1;int UH=begin;while(head<=tail){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:vector<int> findSubstring(string s, vector<string>& words) {vector<int>res;vector<string>table;string str;int size=words.size();GetRes(res,str,size,0,s,words,table);int border=table.size();int UH=s.size();for(int i=0;i<border;i++){int begin=0,end=table[i].size()-1;while(end<UH&&begin<=end){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(vector<int>&res,string str,int size,int now,string&s,vector<string>words,vector<string>&table){if(now==size){if(find(table.begin(),table.end(),str)==table.end())table.push_back(str);return;}for(int i=0;i<size;i++){if(words[i]=="")continue;string temp=str;temp+=words[i];string UH=words[i];words[i]="";GetRes(res,temp,size,now+1,s,words,table);words[i]=UH;}}void rever(string&s,string str,int begin,int end,vector<int>&res){int head=0,tail=str.size()-1;int UH=begin;while(head<=tail){if(str[head]!=s[begin]||str[tail]!=s[end])return;begin++;end--;head++;tail--;}res.push_back(UH);}
};

        （3）另辟蹊径法（会超时）

                上面的方法，我尽可能优化过了，没办法，只好推倒重来了

class Solution {
public:vector<int> findSubstring(string s, vector<string>& words) {vector<int>res;int cap=words[0].size();int size=words.size()*cap;for(int i=0;i<s.size();i++){int end=i+size-1;if(end<s.size()&&GetRes(s,i,end,cap,words))res.push_back(i);}return res;}
private:bool GetRes(string&s,int begin,int end,int cap,vector<string>words){while(begin<=end){string str=s.substr(begin,cap);int i=0;for(i;i<words.size();i++){if(words[i]==str){words[i]="";i=-1;break;}}if(i!=-1)return false;begin+=cap;}return true;}
};

        （4）处理了明显不是起始位置的位置（会超时）

class Solution {
public:vector<int> findSubstring(string s, vector<string>& words) {unordered_map<char,bool>head;unordered_map<string,int>hash;vector<int>res;for(string&word:words){head[word[0]]=true;hash[word]++;}int cap=words[0].size();int room=cap*words.size();int border=s.size();for(int i=0;i<border;i++){int end=i+room-1;if(end<border&&head.find(s[i])!=head.end()&&Check(s,i,end,hash,cap))res.push_back(i);}return res;}
private:bool Check(string&s,int begin,int end,unordered_map<string,int> hash,int cap){while(begin<=end){string str=s.substr(begin,cap);hash[str];if(hash[str]==0)return false;hash[str]--;begin+=cap;}return true;}
};

                这是对上述方法的优化

        （5）绞尽脑汁修改了一下（超时）

                我尽力又再次修改了一下，但还是不过

class Solution {
public:vector<int> findSubstring(string s, vector<string>& words) {unordered_map<char,bool>head;unordered_map<string,int>hash;vector<int>res;for(string&word:words){head[word[0]]=true;hash[word]++;}int cap=words[0].size();int room=cap*words.size();int border=s.size();if(room>border)return res;for(int i=0;i<=border-room;i++){if(head.find(s[i])!=head.end()&&Check(s,i,i+room-1,hash,cap))res.push_back(i);}return res;}
private:bool Check(string&s,int begin,int end,unordered_map<string,int> hash,int cap){while(begin<=end){string str=s.substr(begin,cap);hash[str];if(hash[str]==0)return false;hash[str]--;begin+=cap;}return true;}
};

        （6）推倒重来吧（已经是我认为我能写出来的最极致的方法了，但还是超时了）

                重新换了个思路，发现还是不行，现阶段我应该是写不出来了，放到以后吧

class Solution {
public:vector<int> findSubstring(string s, vector<string>& words) {unordered_map<char,bool>head;vector<int>res;int cap=words[0].size();int room=cap*words.size();int border=s.size();if (room>border)return res;for(string&word:words)head[word[0]]=true;unordered_map<string,int>wordCount;for(string&word:words)wordCount[word]++;for(int i=0;i<=border-room;i++) {if(!head.count(s[i]))continue;unordered_map<string,int>temp;for(int j=i;j<i+room;j+=cap){string str=s.substr(j,cap);if(!head.count(str[0]))break;temp[str]++;}if(temp==wordCount)res.push_back(i);}return res;}
};

这次的题解，看看就行了，毕竟我写的代码哪个都没通过，还是有点丢人的，你可以参考一下我这种优化，优化不行就换思路的方法和不服输的精神，坚持不懈的毅力嘛

等以后再重写这道题吧，暂时放弃了