[Leetcode] Minimum Window Substring 最小字符串窗口

Yuanf 發(fā)布于2019-08-14 12:26 / 1459人閱讀

摘要：雙指針法復雜度時間空間思路用一個哈希表記錄目標字符串每個字母的個數(shù)，一個哈希表記錄窗口中每個字母的個數(shù)。先找到第一個有效的窗口，用兩個指針標出它的上界和下界。

Minimum Window Substring

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).
For example, S = "ADOBECODEBANC" T = "ABC" Minimum window is "BANC".
Note: If there is no such window in S that covers all characters in T, return the emtpy string "".
If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

雙指針法 復雜度

時間 O(N) 空間 O(1)

思路

用一個哈希表記錄目標字符串每個字母的個數(shù)，一個哈希表記錄窗口中每個字母的個數(shù)。先找到第一個有效的窗口，用兩個指針標出它的上界和下界。然后每次窗口右界向右移時，將左邊盡可能的右縮，右縮的條件是窗口中字母的個數(shù)不小于目標字符串中字母的個數(shù)。

注意

用一個數(shù)組來保存每個字符出現(xiàn)的次數(shù)，比哈希表容易

保存結(jié)果子串的起始點初值為-1，方便最后判斷是否有正確結(jié)果

代碼

public class Solution {
    public String minWindow(String S, String T) {
        int[] srcHash = new int[255];
        // 記錄目標字符串每個字母出現(xiàn)次數(shù)
        for(int i = 0; i < T.length(); i++){
            srcHash[T.charAt(i)]++;
        }
        int start = 0,i= 0;
        // 用于記錄窗口內(nèi)每個字母出現(xiàn)次數(shù) 
        int[] destHash = new int[255];
        int found = 0;
        int begin = -1, end = S.length(), minLength = S.length();
        for(start = i = 0; i < S.length(); i++){
            // 每來一個字符給它的出現(xiàn)次數(shù)加1
            destHash[S.charAt(i)]++;
            // 如果加1后這個字符的數(shù)量不超過目標串中該字符的數(shù)量，則找到了一個匹配字符
            if(destHash[S.charAt(i)] <= srcHash[S.charAt(i)]) found++;
            // 如果找到的匹配字符數(shù)等于目標串長度，說明找到了一個符合要求的子串    
            if(found == T.length()){
                // 將開頭沒用的都跳過，沒用是指該字符出現(xiàn)次數(shù)超過了目標串中出現(xiàn)的次數(shù)，并把它們出現(xiàn)次數(shù)都減1
                while(start < i && destHash[S.charAt(start)] > srcHash[S.charAt(start)]){
                    destHash[S.charAt(start)]--;
                    start++;
                }
                // 這時候start指向該子串開頭的字母，判斷該子串長度
                if(i - start < minLength){
                    minLength = i - start;
                    begin = start;
                    end = i;
                }
                // 把開頭的這個匹配字符跳過，并將匹配字符數(shù)減1
                destHash[S.charAt(start)]--;
                found--;
                // 子串起始位置加1，我們開始看下一個子串了
                start++;
            }
        }
        // 如果begin沒有修改過，返回空
        return begin == -1 ? "" : S.substring(begin,end + 1);
    }
}

GPU云服務器云服務器 Window窗口對象最小覆蓋窗口算法 Minimum LeetCode

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://specialneedsforspecialkids.com/yun/64475.html

[leetcode] Minimum Window Substring

摘要：使用而不是因為我們需要的是最值，中間值我們不在乎，所以一次收斂到最小。下面來三個需要查重并且記錄上次出現(xiàn)的位置，選擇以為例，走到用做檢查，發(fā)現(xiàn)出現(xiàn)過，把移到的下一個。是上個題目的簡易版，或者特殊版。這里聊一聊解一類問題，就是滿足某一條件的substring最值問題。最開始我們以Minimum Window Substring為例，并整理總結(jié)leetcode里所有類似題目的通解。 Gi...

Pines_Cheng 2019-08-14 17:17 評論0 收藏0
Leetcode[76] Minimum Window Substring

LeetCode[76] Minimum Window Substring Given a string S and a string T, find the minimum window in S whichwill contain all the characters in T in complexity O(n). For example, S = ADOBECODEBANC T = AB...

suemi 2019-08-16 10:26 評論0 收藏0
[LintCode/LeetCode] Minimum Window Substring

Problem Given a string source and a string target, find the minimum window in source which will contain all the characters in target. Notice If there is no such window in source that covers all charac...

Corwien 2019-08-14 15:43 評論0 收藏0
leetcode-76-Minimum Window Substring

摘要：逐步逼近法，類似于牛頓迭代法。重點是找到規(guī)律，然后將規(guī)律加以表示。動態(tài)規(guī)劃，相鄰兩個位置之間的關系。字符串的疊加，可以增加共性，通過相減可以得到邊界位置處符合規(guī)律的要求。學會將問題轉(zhuǎn)化為可求的邊界問題。吃透題目：任何問題的解決在于理解題目，挖掘本質(zhì)。這道題目，從一個string中找包含char的最小子序列，O(n)，要求只能遍歷一遍。每次移動一個index，都嘗試找子序列，通...

edagarli 2019-07-31 11:10 評論0 收藏0
[LeetCode] 727. Minimum Window Subsequence

Problem Given strings S and T, find the minimum (contiguous) substring W of S, so that T is a subsequence of W. If there is no such window in S that covers all characters in T, return the empty string...

kaka 2019-08-16 13:55 評論0 收藏0