题目

给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。

注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。

 

示例 1：

//输入：
  let s = "barfoothefoobarman",
  let words = ["foo","bar"]
//输出：
[0,9]
//解释：
//从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。
//输出的顺序不重要, [9,0] 也是有效答案。

示例 2：

//输入：
  let s = "wordgoodgoodgoodbestword",
  let words = ["word","good","best","word"]
//输出：
[]

解答

var findSubstring = function(s, words) {
    let len;
    if(words.length>0){
        len=words[0].length;
    }

    return   existsStr(s,words,len);
};
function initListMap(list){
    let map={};
    for(let i of list){
        if(!map[i]){
            map[i]={start:0};
        }
        map[i].start+=1;
    }
    return map;
}
function formateListMap(map){
    for(let i in map){
        map[i]["exist"]=map[i].start;
    }
}
function existsStr(str,list,len){
    let rst=[];
    if(len){
        let long=len*list.length;
        let listMap=initListMap(list);
        for(let i=0;i+long<=str.length;i++){
            let st=str.substr(i,long);
            formateListMap(listMap);
            let exist=true;
            for(let k=0;k<long;k+=len){
                let s=st.substr(k,len);
                if(listMap[s]&&listMap[s].exist>0){
                    listMap[s].exist=listMap[s].exist-1;
                }else {
                    exist=false;
                    break;
                }
            }
            if(!exist){
                continue;
            }
            rst.push(i);
        }
    }
    return rst;
}
Last modification：December 9th, 2019 at 11:13 am
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏