30_串联所有单词的子串

题目

30_串联所有单词的子串

 

分析题目

  • 题目意思并不难,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);
       }
    }

 

上一篇:Egret入门学习日记 --- 第三十九篇(书中 11.12 ~ 11.15 节 内容)


下一篇:smobiler仿自如app筛选页面