题目
分析题目
- 题目意思并不难,words数组里面的所有字符串和s字符串连续匹配,但难点就在于,words里面字符串顺序是不固定的。
- 我首先想到的是用Map来进行快速匹配,但要注意,map里面键相同时后面的值会覆盖前面的值,一开始没注意这点导致我的结果数组里的值比官方数组值个数多。
- Map键存储各个words里面的字符串,值是出现个数(弥补了不能map结构不能重复的特性)
- let map=map1 当map 变动时map1也会改变
代码
创建map,将words的内容放到map中。其中map的key是words的各个字符串,value是各个字符串出现次数
let map = new Map(); for (let i = 0; i < words.length; i++) { if(map.has(words[i])){ let t= map.get(words[i]) map.set(words[i],t+1); } else map.set(words[i], 1); }
map2是map的深拷贝,为了方便我们将words里面一个一个字符串长度定义为eachlen,ans是结果数组
let map2=cloneMap(map); let eachlen = words[0].length; let ans = [];
cloneMap函数使克隆后的map与之前的map互不影响
function cloneMap(map) { let obj= Object.create(null); for (let[k,v] of map) { obj[k] = v; } obj = JSON.stringify(obj); obj = JSON.parse(obj); let tmpMap = new Map(); for (let k of Object.keys(obj)) { tmpMap.set(k,obj[k]); } return tmpMap; }
我选择从第一个元素遍历到,第s.length - words.length * eachlen个元素,为什么不是遍历到最后一个呢?没有必要,如果当前位置加上words所有元素总长度超过s的长度,没有必要考虑。
k1是我截取的第一个字符串,如果在map里找不到对应的,就没必要往下走了,直接看i的下一个取值。如果在map里找到了对应的,将i2定义为i+eachlen,开始下一个words元素的匹配,匹配成功i2继续
移动,匹配失败跳出匹配循环。flag是用来检测map的value是否全部为0的,全为0则匹配成功,将i压入结果栈,否则不压入。最后要对map里面的键值对 “初始化”,将map2克隆给map。这就是我为什么
设置一个map2并且一定要深拷贝的原因
for (let i = 0; i <= s.length - words.length * eachlen; i++) { let k1=s.substr(i,eachlen); if(map.has(k1)) { map.set(k1,map.get(k1)-1); let i2=i+eachlen; for(let j=0;j<words.length-1;j++){ let str=s.substr(i2,eachlen); if(map.has(str)) map.set(str,map.get(str)-1); else break; i2=i2+eachlen; } let flag=1; map.forEach((value,key)=>{ if(value!=0) flag=0; }) if(flag==1) //满足 ans.push(i); map=cloneMap(map2); } }