2020-06-29 30. Substring with Co

https://leetcode.com/problems/substring-with-concatenation-of-all-words/

My answer / NAC

/**
 * @param {string} s
 * @param {string[]} words
 * @return {number[]}
 */
var findSubstring = function(s, words) {
    let map = {};
    let countWords;
    let begin = 0, end = 0;
    let len = words[0].length;
    let res = [];
    
    for(let i=0; i<words.length; i++){
        if(map[words[i]]==null) map[words[i]] = 1;
        else {
            map[words[i]]++;
        }
    }
    countWords = Object.keys(map).length;
    
    while(begin<s.length) {
        
        if(countWords==0){
            
            begin = begin-len*words.length;
            res.push(begin);
            
            
            let current = s.slice(begin, begin+len);
            if(map[current]!=null) {
                map[current]=1;
                begin+=len;
            } else {
                begin++;
            }
            if(map[current]>0) countWords++; 
            

        } else {
            
            let current = s.slice(begin, begin+len);
            if(map[current] != null) {
                map[current]--;
                begin+=len;
            } else {
                begin++;
            }
            if(map[current]==0) countWords--;
        }
    }
    return res;
};

Best answer

/**
 * @param {string} s
 * @param {string[]} words
 * @return {number[]}
 */
var findSubstring = function(s, words) {
    if(words.length==0) return [];
    
    let allWords = {};
    let numWords;
    let len = words[0].length;
    let res = [];
    

    
    for(let i=0; i<words.length; i++){
        if(allWords[words[i]]==null) allWords[words[i]] = 1;
        else {
            allWords[words[i]]++;
        }
    }
    
    // numWords = Object.keys(allWords).length; //这里的numWords不是指所有key的个数，而是就指我们要包含它里面所有元素的那个数组的长度
    numWords = words.length;
    for(let i=0; i<s.length-numWords*len+1; i++){
        let hasWords = {};
        let num = 0;
        while(num < numWords) {
            let str = s.substring(i+num*len, i+(num+1)*len);
            // 当前字符串不存在要找的数组里
            if(allWords[str]!=null) {
                if(hasWords[str]==null) hasWords[str] = 1;
                else hasWords[str]++;
                
                if(hasWords[str]>allWords[str]) {
                    break;
                }
            } else {
                break;
            }
            num++;
        }
        if(num == numWords) {
            res.push(i);
        }
    }
    
    return res;
};

• hasWords是一个工具Map，作用只是用来判断当前的子字符串中是否符合要求，一旦出现不符合的两种情形（a.字符串不在要求的单词里，b.相同的字符串多于我们想要的）之一就break跳过。
• 抄的时候忽略了numWords在这里的意义是数组的长度而不是map中keys的个数

一个大神写的leetcode全集，非常用心和厉害。讲的HashMap思路很清晰，
https://leetcode.wang/leetCode-30-Substring-with-Concatenation-of-All-Words.html

Recap

Map能够处理字符串比对问题。学会这种思考方式：一个Map能够判断一个子串是否符合一个数组的若干组合。