BD真题 2020-06-29 76. Minimum Wind

https://leetcode.com/problems/minimum-window-substring/

My answer / AC

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function(s, t) {
    let left = 0, right = -1;
    let min="", countChar;
    let map = {};
    for(let i=0; i<t.length; i++){
        if(map[t[i]]==null) map[t[i]] = 1;
        else if(map[t[i]]>0) map[t[i]]++;
    }
    countChar = Object.keys(map).length;
    while(right<s.length) {
        if(countChar==0) {
            let current = s[left];
            if(map[current]!=null) map[current]++;
            if(map[current]>0) countChar++;
            
            
            
            let temp = s.substring(left, right+1);
            if(min=="") min=temp;
            else 
                min = min.length>temp.length ? temp : min;
            
            left++;
            
        } else {
            right++;
            let current = s[right];
            if(map[current]!=null) map[current]--;
            if(map[current]==0) countChar--;
        }
    }
    return min;
};

重点关注

• map的key用来存储每个t中字符，value用来存储该字符出现次数。
• countChar用来表示t中的所有字符的废留，即还有多少个字符能够实现valid。如果t中没有重复字符，那么countChar中存的就是当前还有多少个字符需要匹配。如果t中存在重复字符，那么可能要匹配多个该重复字符countChar才能减1。

参考这里的，注释很详细
https://leetcode.com/problems/minimum-window-substring/discuss/411388/JavaScript-Solution-w-Detailed-Comments

Recap

字符串的匹配要灵活运用指针，map以及临时变量current、countChar等。