30. 串联所有单词的子串

给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。

示例 1：

输入： s = "barfoothefoobarman", words = ["foo","bar"] 输出：[0,9]

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

示例 2：

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

1.由于子串不需要考虑 words 中单词出现的顺序，并且words中可能会出现重复单词，所以不能用 set 来存储words，我们可以用map来存储words，把words中的单词作为key，单词出现的次数作为value;

2.循环字符串s，然后每次从字符串s中截取一段长度为 words 单词总长的字符串，然后按照单个words单词的长度，对其进行拆分成单词;

3.使用拆分后的单词去map中查询，如果存在，则将其 value - 1，否则表明当前字符串不符合要求，直接break跳出当前循环;

4.内层循环结束后，如果map所有的 value 都为0，则表明当前子字符串符合要求，将其起始索引放入结果集中

5.最后返回结果集

时间复杂度：O(KN) N 为 s 的长度，K 为 words 一个单词的长度

空间复杂度：O(N + M) N 为 s 的长度，M 为 words 的长度

var findSubstring = function(s, words) {
    let res = []
    if(s===null||s.length===0||words===null||words.length===0){
        return res
    }
    const wordLen = words[0].length
    const allWordsLength = words.length*wordLen
    const obj = {}
    words.map((word)=>{
        obj[word]?obj[word]++:obj[word]=1
    })
    for(let i=0;i<s.length-allWordsLength+1;i++){
        const vm = Object.assign({},obj)
        for(let j=i;j<i+allWordsLength-wordLen+1;j += wordLen){
            let item =s.substr(j,wordLen) 
            if(vm[item]){
                vm[item]--
            }else {
                break
            }
        }
        if(Object.values(vm).every((val)=>val===0)){
            res.push(i)
        }
    }
    return res
};

1.使用两个对象，windows 和 needs，windows存储s的子串，needs存储words，并且使用两个指针 l 和 r,表示一个窗口的左右两边的索引

2.外层循环索引 i 从 0 开始，并且 i < wordLength 只用循环一个单词的长度

3.内层循环从 i 开始，l = r = i，依次进行截取 let w1 = s.slice(i, i + wordLength )，判断截取的单词w1 是否存在于存储 needs 中，如果不存在，则直接continue跳过当前循环

4.如果存在则将其添加到 windows 中，如果 windows[w1] === needs[w1]则将count++，表示一个单词已经准备就绪

5.如果 count === Object.keys(needs).length，则表示所有的单词都已经准备就绪，由于有可能会出现多个重复的符合要求的单词，所以此时还需要判断 r - l === words所有单词的长度和

6.如果条件成立则表示当前子字符串符合要求，将子字符串的起始索引l，放入结果集中 res.push(l)

7.从窗口的左边截取子字符串 let w2 = s.slice(l, l + wordLength)，如果 w2 存在于 needs 中，则windows[w2]--，并且如果 windows[w2] < needs[w2]，则count--

8.最后返回结果集

时间复杂度：O(N) 外层循环时间复杂度为O(K)，K 为 words 一个单词的长度内层循环时间复杂度为 O(2 N / K)，即 l和r从字符串起始索引遍历到结束索引，每次递加K 所以，时间复杂度为 O(K 2 * N / K) = O(2N) => O(N)

空间复杂度：O(N + M) N 为 s 的长度，M 为 words 的长度

var findSubstring = function(s, words) {
    const res = []
    if(!words||words.length===0){
        return res
    }
    let windows = {}
    const needs ={}
    let count = 0
    let l=0,r=0
    const wordLength = words[0].length
    for(let i=0;i<words.length;i++){
        let item = words[i]
        needs[item]?needs[item]++:needs[item]=1
    }
    for(let i=0;i<wordLength;i++){
        windows = {}
        l=r=i
        count = 0
        while(r<s.length-wordLength){
            let w1 = s.slice(r,r+wordLength)
            r += wordLength
            if(!needs[w1]){
                l = r
                windows = {}
                count = 0
                continue
            }
            windows[w1]?windows[w1]++:windows[w1]=1
            if(windows[w1]===needs[w1])count++
            const keyLength = Object.keys(needs).length
            while(count===keyLength){
                if(r-l === wordLength*words.length){
                    res.push(l)
                }
                let w2 = s.slice(l,l+wordLength)
                l += wordLength
                if(needs[w2]){
                    windows[w2]--
                    if(windows[w2]<needs[w2]){
                        count--
                    }
                }
            }
        }
    }
    return res
};

blueWind123731 / algorithm_learning

30. 串联所有单词的子串 #6