30.拼接所有单词的子串-算法（leetode，附思维导图+全解）300题

零题：算法（leetode，附思维导图+全解）300题（30）拼接所有单词子串1标题描述2解概览（思维导图）3所有方案1方案11)代码：//方案1《普通滑动窗口法》。//Tips://1）一般来说，字符串还是挺适合“滑动窗口”的（“总之算法和数据结构都适合~”）。//思路：//1)状态初始化。结果索引存储在数组resArr中。//2）“滑动窗口”，核心：通过下标i穷举所有可能的子串tempS。//2.1)根据单个单词的长度（oneWordLength）得到tempS的每一段（substr）。//2.1.1)如果此时tempWords中不包含当前substr，则直接退出本次循环处理。//2.1.2)如果tempWords包含当前段（substr），那么tempWords会清空对应的substr。//2.2)此时确定tempWords的长度。如果tempWords.length===0，则表示满足条件，将下标i放入结果数组resArr中。//3)返回结果数组resArr。varfindSubstring=function(s,words){//1)状态初始化。结果索引存储在数组resArr中。constsLength=s.length,oneWordLength=words[0].length,wordsLength=words.length,wordStrLength=wordsLength*oneWordLength;让resArr=[];//2）“滑动窗口”，核心：通过下标ipoor列出所有可能的子串tempS。for(leti=0;i<=(sLength-wordStrLength);i++){consttempS=s.substr(i,wordStrLength),tempSLength=tempS.length,tempWords=JSON.parse(JSON.stringify(words))};//2.1)根据单个单词的长度（oneWordLength）得到tempS的每一段（substr）。对于(letindex=0;index<=(tempSLength-oneWordLength);index+=oneWordLength){constsubstr=tempS.substr(index,oneWordLength);//2.1.1)如果tempWords不包含当前段（substr），则直接退出本次循环处理。如果(!(tempWords.includes(substr))){中断;}//2.1.2)如果此时tempWords包含当前段（substr），则tempWords会清空对应的substr。else{constdeleteIndex=tempWords.indexOf(substr);tempWords.splice(deleteIndex,1);}}//2.2)此时确定tempWords的长度。如果tempWords.length===0，则表示满足条件，将下标i放入结果数组resArr中。如果(tempWords.length===0){resArr.push(i);}}//3)返回结果数组resArr。returnresArr;}2Scheme21)Code://Scheme2"slidingwindow+hash+recursion".//Tips:当涉及到“映射、数量、重复性（即去重）、唯一性（即次数）等”时，可以优先考虑hash（对应JS中的map数据结构）。//思路：//1)状态初始化。结果索引存储在数组resArr中。//2)遍历单词，将单词数组数据存储到map中（便于读取等操作）。//3)穷举所有可能的字符子串并调用递归函数。//4)返回结果数组resAr。varfindSubstring=function(s,words){//递归constdfs=(index=0,substr='',map=newMap(),resArr=[])=>{consttempStr=substr.substr(0,一个字长）；//1)递归退出。if(substr.length===oneWordLength&&map.get(tempStr)===1){resArr.push(index);返回;}if(!map.has(tempStr)||map.get(tempStr)<=0){返回;}//2)递归主体。不断更新substr和map，然后不断调用递归处理函数dfs。substr=substr.substr(oneWordLength);map.set(tempStr,map.get(tempStr)-1);dfs（索引，substr，地图，resArr）；};//1)状态初始化。结果索引存储在数组resArr中。constsLength=s.length,oneWordLength=words[0].length,wordsLength=words.length,wordStrLength=wordsLength*oneWordLength;让resArr=[],map=newMap();//2）遍历words，将words数组数据存入map（方便读取等操作）。for(leti=0;itempMap.set(key,value));dfs(i,substr,tempMap,resArr);}//4)返回结果数组resAr。returnresArr;}3Scheme31)代码：//Scheme3“递归”。//Tips：永远记住recursion=recursionexit（为了不陷入无线递归的死循环）+recursionbody（一般在改变一些参数后，调用函数本身）。//一般递归出口放在前面，递归体放在后面。//思路：//1)状态初始化。结果索引存储在数组resArr中。//2)不断枚举所有子串，调用递归函数。//如果递归函数的处理结果符合预期，将下标i存入结果数组resAr。//3)返回结果数组resAr。varfindSubstring=function(s,words){//递归constdfs=(index=0,substr='',words=[],resArr=[])=>{consttempStr=substr.substr(0,oneWordLength);//1)递归退出。if(substr.length===oneWordLength&&words[0]===substr){resArr.push(index);返回;}if(!words.includes(tempStr)){返回；}//2)递归体。处理完substr和words，继续调用递归函数dfs。substr=substr.substr(oneWordLength);constdeleteIndex=words.indexOf(tempStr);words.splice(deleteIndex,1);dfs(index,substr,words,resArr);};//1)状态初始化。结果索引存储在数组resArr中。constsLength=s.length,oneWordLength=words[0].length,wordsLength=words.length,wordStrLength=wordsLength*oneWordLength;让resArr=[];//2)不断枚举所有子串，调用递归函数。//如果递归函数的处理结果符合预期，将下标i存入结果数组resAr。for(leti=0;i<=(sLength-wordStrLength);i++){constsubstr=s.substr(i,wordStrLength);}//边界：单词的深拷贝！！consttempWords=JSON.parse(JSON.stringify(words));dfs(i,substr,tempWords,resArr);}//3)返回结果数组resAr。returnresArr;}四更1刷题进度1)LeetCode:307/2390.2)《剑指offer》:66/66.3）相关学习资料和笔记汇总：https://github.com/CYBYOB/algorithm-leetcode/tree/master/data%26notes。4）注：所有题目大概有2-5个解答，以后会不断更新题解。敬请关注~欢迎大家进群学习交流解决问题拿高薪~2GitHub-LeetCode项目仓库0）本项目地址：https://github.com/CYBYOB/algorithm-leetcode.目标与愿景：让大家具备一定的算法能力，在面试中应对算法（能举一反三的同学也能融入自己的肌肉和血液，甚至为公司的业务和技术赋能）。我还是每周更新——保证每周都有新题和新解，刺激你的神经和刷题欲望。欢迎对算法感兴趣的同学加入我们的社区。QQ群：933919972；作者QQ：1520112971；作者VX：c13227839870（可以拉你进群，一起学习交流~）。3作者标签1）《BAT小伪全栈工程师，专注前端，偶尔写点后端》。2）2019微信小程序应用开发大赛-全国三等奖；2019CODA大赛-Top17/211并获得“优秀团队”等称号3）“半自媒体人”，在校期间，个人公众号（IT三少。新自媒体(公众号)编号：马农三少）半年内实现0到5.8K+粉丝增长等。