[leetcode] Minimum Window Substring
2020-12-13 03:41
标签：style blog http color strong os 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, Minimum window is Note: If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S. https://oj.leetcode.com/problems/minimum-window-substring/ 思路：窗口移动法。 详见这里 [leetcode] Minimum Window Substring,搜素材,soscw.com [leetcode] Minimum Window Substring 标签：style blog http color strong os 原文地址：http://www.cnblogs.com/jdflyfly/p/3815275.html
S = "ADOBECODEBANC"
T = "ABC""BANC".
If there is no such window in S that covers all characters in T, return the emtpy string "".
public class Solution {
public String minWindow(String S, String T) {
if (S == null || T == null)
return "";
int[] needToFind = new int[256];
int[] found = new int[256];
for (int i = 0; i )
needToFind[T.charAt(i)]++;
String result = "";
int begin = 0, end = 0;
int minWin = Integer.MAX_VALUE;
int count = 0;
for (end = 0; end ) {
if (needToFind[S.charAt(end)] == 0)
continue;
char ch = S.charAt(end);
found[ch]++;
if (found[ch] needToFind[ch])
count++;
if (count == T.length()) {
//move the begin pointer while the constrain meets
while (begin S.length()
&& (found[S.charAt(begin)] > needToFind[S.charAt(begin)] || needToFind[S.charAt(begin)] == 0)) {
if (found[S.charAt(begin)] > 0)
found[S.charAt(begin)]--;
begin++;
}
//update the min according to the current window
if (end - begin + 1 minWin) {
minWin = end - begin + 1;
result = S.substring(begin, end + 1);
}
}
}
return result;
}
public static void main(String[] args) {
System.out.println(new Solution().minWindow("ADOBECODEBANC", "ABC"));
}
}
文章标题：[leetcode] Minimum Window Substring
文章链接：http://soscw.com/essay/28107.html