Leetcode[76] Minimum Window Substring

suemi 發布于2019-08-16 10:26 / 905人閱讀

LeetCode[76] 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".

Hash Table + Two Pointer

復雜度
O(N),O(N)

思路
類似two pointer的想法。每次維護一個窗口。

代碼

public String minWindow(String s, String t) {
    int start = 0, len = Integer.MAX_VALUE;
    int[] times = new int[256];
    int[] stimes = new int[256];
    for(int i = 0; i < t.length(); i ++) {
        times[t.charAt(i)] ++;
    }
    int cnt = 0;
    int begin = -1, end = 0;
    for(int i = 0; i < s.length(); i ++) {
        char ch = s.charAt(i);
        stimes[ch] ++;
        if(stimes[ch] <= times[ch]) cnt ++;
        if(cnt == t.length()) {
            while(start < s.length() && stimes[s.charAt(start)] > times[s.charAt(start)]) {
                stimes[s.charAt(start)] --;
                start ++;
            }
            //
            if(i - start + 1 < len) {
                begin = start;
                end = i;
                len = i - start + 1;
            }
            stimes[s.charAt(start)] --;
            start ++;
            cnt --;
        }
    }
    return begin == -1 ? "" : s.substring(begin, end + 1);
}

云服務器 GPU云服務器 Minimum 服務器ipv76 LeetCode Substring

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/69806.html

leetcode-76-Minimum Window Substring

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

edagarli 2019-07-31 11:10 評論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] Minimum Window Substring

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

Pines_Cheng 2019-08-14 17:17 評論0 收藏0
[Leetcode] Minimum Window Substring 最小字符串窗口

摘要：雙指針法復雜度時間空間思路用一個哈希表記錄目標字符串每個字母的個數，一個哈希表記錄窗口中每個字母的個數。先找到第一個有效的窗口，用兩個指針標出它的上界和下界。 Minimum Window Substring Given a string S and a string T, find the minimum window in S which will contain all the...

Yuanf 2019-08-14 12:26 評論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