[leetcode] Minimum Window Substring

Pines_Cheng 發(fā)布于2019-08-14 17:17 / 722人閱讀

摘要：使用而不是因?yàn)槲覀冃枰氖亲钪担虚g值我們不在乎，所以一次收斂到最小。下面來三個(gè)需要查重并且記錄上次出現(xiàn)的位置，選擇以為例，走到用做檢查，發(fā)現(xiàn)出現(xiàn)過，把移到的下一個(gè)。是上個(gè)題目的簡(jiǎn)易版，或者特殊版。

這里聊一聊解一類問題，就是滿足某一條件的substring最值問題。
最開始我們以Minimum Window Substring為例，并整理總結(jié)leetcode里所有類似題目的通解。

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
S = "ADOBECODEBANC" , T = "ABC", Minimum window is "BANC".

我們要把問題拆解成三個(gè)字問題：唯一的表示substring, 檢查substring是否符合要求，記錄最值。
1.
如何唯一的表示一個(gè)substring, 有兩種方法，一種用頭尾指針，一種用尾指針加substring長(zhǎng)度。
2.
檢查substring是否符合要求，這道題目要求包含T中的每個(gè)字母，所以我們需要一個(gè)counter來記錄T里每個(gè)character出現(xiàn)的次數(shù)，空間O(26) O(128) O(256) 都行，可以和面試官討論。類似題目唯一變化的就是這個(gè)部分，可以是每個(gè)字符只能出現(xiàn)一次，最多出現(xiàn)兩個(gè)不同字符，每個(gè)字符最多出現(xiàn)K次等等。
3.
記錄最值。根據(jù)掃描方法的不同，長(zhǎng)度有時(shí)為r-l,此時(shí)r不包含在substring里，有時(shí)為r-l+1,此時(shí)包含在substring里。

這篇博客主要講第二個(gè)子問題，如何判斷substring是否符合要求。以Minimum Window Substring為例。

public class Solution {
    public String minWindow(String s, String t) {
        // empty check
        if(s == null || t == null || s.length() == 0 || t.length() == 0) return "";
        // initial counter for valid check
        int[] counter = new int[128];
        for(char c : t.toCharArray()){
            counter[c]++;
        }
        // variables help represent substring and min/max
        char[] chs = s.toCharArray();
        // 變量名解釋，i表示頭即先開始掃描的指針，j表示尾。i,j對(duì)counter的操作相反，一個(gè)加一個(gè)減或者一個(gè)減一個(gè)加。 
        // 上面的counter記錄每個(gè)字符出現(xiàn)次數(shù)，count表示substring里滿足條件的字符出現(xiàn)總次數(shù)（可以從0加到count,也可以從count減少到0.
        int j = 0, i=0, minLen = Integer.MAX_VALUE, start = 0, count = t.length();
        
        //這里可以使用for和while兩種循環(huán)，個(gè)人偏向for, 因?yàn)閕指針要一次走一個(gè)字符遍歷完整個(gè)string.
        for( ; i < chs.length; i++){      //逐個(gè)掃描
            // 我們包含了第i個(gè)元素，并且要立即判斷是否滿足條件。使用--x, 而不是x--.
            if(--counter[chs[i]] > -1) {
                count--;
            }
            // 因?yàn)槲覀冃枰氖亲钪担虚g值我們不在乎，所以一次收斂到最小。
            while(count == 0) {     // 快速收緊
                if(i -j + 1< minLen) {
                    minLen = i - j + 1;
                    start = j;
                }
                // 用 == 0 判斷是因?yàn)橛械膕ubstring里個(gè)別字符可能偏多，多余的字符不會(huì)算作滿足條件。下方有簡(jiǎn)單的例子。 
                // 一次只移動(dòng)一個(gè)char, 所以這里用 == 0
                if(counter[chs[j++]]++ == 0) {
                    count++;
                }
            }
        }
        
        return minLen == Integer.MAX_VALUE ? "" : new String(chs, start, minLen);
    }
}

X表示占位符，不是字母X。（使用空格會(huì)被自動(dòng)消除，所以這里用了X）
S: ADOBECODEBANC T: ABC
i: ADOBECXXXXXXXX
j: XDOBECXXXXXXX
i: XDOBECODEBAXX
j: XXXXXXODEBAXX
注意這一步j(luò)最后落在了C后面，而不是B的后面。因?yàn)锽在T里只出現(xiàn)了一次, i在掃描的時(shí)候會(huì)減小兩次，counter[B] = -1, counter[c] = 0
i: XXXXXXODEBANC
j: XXXXXXXXXBANC

將S，T里字符換成String,變成Leetcode 30, Substring with Concatenation of All Words. 
You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters. 
s: "barfoothefoobarman",  words: ["foo", "bar"], You should return the indices: [0,9]

字符長(zhǎng)度為K，我們可能從0， 1， 2， K-1開始組成不同字符，從K開始會(huì)和從O開始重合了。代碼如下，不過多解釋，可以直接跳過。

public class Solution {
    public List findSubstring(String s, String[] words) {
        List res = new ArrayList();
        int N = s.length(), M = words.length, K = words[0].length();
        // check input
        if(s == null || K == 0 || N < M*K) return res;
        Map map = new HashMap<>(), curMap = new HashMap<>();
        // initial counter
        for(String word: words) {
            map.put(word, map.getOrDefault(word,0) + 1);
        }
        // str denote first word, temp denote last word
        String str = null, temp = null;
        for(int i=0; i< K; i++) { 
            int count = 0;
            // two poniter scan, each time move K steps
            for(int l=i, r=i; r+K <= N; r += K) {
                str = s.substring(r, r+K);
                if(map.containsKey(str)) {
                    curMap.put(str, curMap.getOrDefault(str,0) + 1);
                    
                    if(curMap.get(str) <= map.get(str)) count++;
                    // has a word above the counter of it
                    while(curMap.get(str) > map.get(str)) {
                        temp = s.substring(l, l+K);
                        curMap.put(temp, curMap.get(temp) - 1);
                        l += K;
                        if(curMap.get(temp) < map.get(temp)) count--;
                    }
                    // should be exactly M, when meet, delete last word
                    if(count == M){
                        res.add(l);
                        temp = s.substring(l, l+K);
                        curMap.put(temp, curMap.get(temp) - 1);
                        l += K;
                        count--;
                    }
                } else {
                    curMap.clear();
                    count = 0;
                    l = r + K;
                }
            }
            curMap.clear();
        }

        return res;
    }
}

下面來三個(gè)longest substring.
LC3 Longest Substring Without Repeating Characters
需要查重并且記錄上次出現(xiàn)的位置，選擇map.
以abcdba為例，i走到b, 用map做檢查，發(fā)現(xiàn)出現(xiàn)過，把j移到map.get(b)的下一個(gè)。
i走到a, 用map做檢查，發(fā)現(xiàn)出現(xiàn)過，把j移到map.get(a)的下一個(gè)。發(fā)現(xiàn)不對(duì)，因?yàn)橄乱粋€(gè)字符是b已經(jīng)出現(xiàn)過兩次，所以需要一個(gè)比較，取map.get(b),map.get(a)的最大值。

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        // empty check
        if(s == null || s.length() == 0) return 0;
        // 
        Map map = new HashMap<>();
        // scan whole string and calculte
        int len = 0;
        char[] chs = s.toCharArray();
        for(int i=0, j=0; i len) {
                len = i-j+1;
            }
        }
        return len;
    }
}

LC340. Longest Substring with At Most K Distinct Characters

Given a string, find the length of the longest substring T that contains at most 2 distinct characters.
For example, Given s = “eceba”,
T is "ece" which its length is 3.

counter記錄每個(gè)字符出現(xiàn)次數(shù)。 count表示有多少個(gè)不同字符，題目要求最多出現(xiàn)k個(gè)。

public class Solution {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        // corner case
        if(s== null || s.length() == 0)  return 0;
        // counter, count denote k
        int[] counter = new int[128];
        // l denote tail, r denote head, two pointer scan
        int j = 0, len = 0, count = 0;
        for(int i=0; i k) { 
                while( --counter[s.charAt(j++)] > 0);   
                count--;
            }
            if(i - j + 1 > len) {
                len = i - j +1;
            }
        }
        // return max
        return len;
    }
}

LC159. Longest Substring with At Most Two Distinct Characters

Given a string, find the length of the longest substring T that contains at most 2 distinct characters.
For example, Given s = “eceba”,
T is "ece" which its length is 3.

是上個(gè)題目的簡(jiǎn)易版，或者特殊版。只有兩個(gè)字符，我們就不需要一個(gè)數(shù)組了，只需要兩個(gè)位置標(biāo)記就行。p1, p2. 為了讓計(jì)算最值方便，讓p1始終小于p2.

這里需要注意的就是p1,p2在repeating characters出現(xiàn)的時(shí)候，同時(shí)會(huì)指向這個(gè)字符串的最后一個(gè)。
在判斷第三個(gè)字符是否出現(xiàn)的時(shí)候，首先要比較p1 != p2.

public class Solution {
    public int lengthOfLongestSubstringTwoDistinct(String s) {
        if(s.isEmpty()) return 0;
        int p1 = 0, p2 = 0, max = 1, len = 1; 
        char[] chs = s.toCharArray();
        for(int i=1; i max) max = len;
                len = i - p1;       // always keep p1,p2 ordered p1<=p2
                p1 = p2;
                p2 = i;
            } else {  
                if(chs[i] == chs[p1]) {  // 0 or repeating charcters lead to p1=p2
                    p1 = p1 == p2 ? i:p2;
                }
                len++;
                p2 = i;
            }
        }
        
        if (len > max) max = len;
        return max;
    }
}

今天先寫到這里，以后補(bǔ)充。