資訊專欄INFORMATION COLUMN
LeetCode[76] Minimum Window Substring
Hash Table + Two PointerGiven 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".
復(fù)雜度
O(N),O(N)
思路
類似two pointer的想法。每次維護(hù)一個(gè)窗口。
代碼
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);
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/69806.html
摘要：逐步逼近法，類似于牛頓迭代法。重點(diǎn)是找到規(guī)律，然后將規(guī)律加以表示。動(dòng)態(tài)規(guī)劃，相鄰兩個(gè)位置之間的關(guān)系。字符串的疊加，可以增加共性，通過(guò)相減可以得到邊界位置處符合規(guī)律的要求。學(xué)會(huì)將問題轉(zhuǎn)化為可求的邊界問題。 吃透題目： 任何問題的解決在于理解題目，挖掘本質(zhì)。 這道題目，從一個(gè)string中找包含char的最小子序列，O(n)，要求只能遍歷一遍。 每次移動(dòng)一個(gè)index，都嘗試找子序列，通...
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...
摘要：使用而不是因?yàn)槲覀冃枰氖亲钪担虚g值我們不在乎，所以一次收斂到最小。下面來(lái)三個(gè)需要查重并且記錄上次出現(xiàn)的位置，選擇以為例，走到用做檢查，發(fā)現(xiàn)出現(xiàn)過(guò)，把移到的下一個(gè)。是上個(gè)題目的簡(jiǎn)易版，或者特殊版。 這里聊一聊解一類問題，就是滿足某一條件的substring最值問題。最開始我們以Minimum Window Substring為例，并整理總結(jié)leetcode里所有類似題目的通解。 Gi...
摘要：雙指針法復(fù)雜度時(shí)間空間思路用一個(gè)哈希表記錄目標(biāo)字符串每個(gè)字母的個(gè)數(shù)，一個(gè)哈希表記錄窗口中每個(gè)字母的個(gè)數(shù)。先找到第一個(gè)有效的窗口，用兩個(gè)指針標(biāo)出它的上界和下界。 Minimum Window Substring Given a string S and a string T, find the minimum window in S which will contain all the...
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...
閱讀 2658·2021-11-25 09:43
閱讀 2759·2021-11-04 16:09
閱讀 1695·2021-10-12 10:13
閱讀 907·2021-09-29 09:35
閱讀 908·2021-08-03 14:03
閱讀 1798·2019-08-30 15:55
閱讀 3023·2019-08-28 18:14
閱讀 3603·2019-08-26 13:43
