不好做的一道題，發現String Algorithm可以出很多很難的題，特別是多指針，DP，數學推導的題。參考了許多資料：
http://leetcode.com/2010/11/finding-minimum-window-in-s-which.html
http://www.geeksforgeeks.org/find-the-smallest-window-in-a-string-containing-all-characters-of-another-string/
leetcode 5？http://tianrunhe.wordpress.com/2013/03/23/minimum-window-substring/
最有用的最后一個資料，因為里面有一個例子詳細說明了如何變化，我加上了一些中文備注：
For example,
S = “ADOBECODEBANC”
T = “ABC”
Minimum window is “BANC”.
leetcode medium。?
Thoughts:
The idea is from?here. I try to rephrase it a little bit here. The general idea is that we find a window first, not necessarily the minimum, but it’s the first one we could find, traveling from the beginning of S. We could easily do this by keeping a count of the target characters we have found. After finding an candidate solution, we try to optimize it. We do this by going forward in S and trying to see if we could replace the first character of our candidate. If we find one, we then find a new candidate and we update our knowledge about the minimum. We keep doing this until we reach the end of S. For the giving example:
- We start with our very first window: “ADOBEC”, windowSize = 6. We now have “A”:1, “B”:1, “C”:1 （保存在needToFind數組里）
- We skip the following character “ODE” since none of them is in our target T. We then see another “B” so we update “B”:2. Our candidate solution starts with an “A” so getting another “B” cannot make us a “trade”. （體現在代碼就是只有滿足hasFound[S.charAt(start)] > needToFind[S.charAt(start)]) 才能移動左指針start）
- We then see another “A” so we update “A”:2. Now we have two “A”s and we know we only need 1. If we keep the new position of this “A” and disregard the old one, we could move forward of our starting position of window. We move from A->D->O->B. Can we keep moving? Yes, since we know we have 2 “B”s so we can also disregard this one. So keep moving until we hit “C”: we only have 1 “C” so we have to stop. Therefore, we have a new candidate solution, “CODEBA”. Our new map is updated to “A”:1, “B”:1, “C”:1.
- We skip the next “N” （這里忽略所有不在T的字符：用needToFind[S.charAt(start)] == 0來判斷） and we arrive at “C”. Now we have two “C”s so we can move forward the starting position of last candidate: we move along this path C->O->D->E until we hit “B”. We only have one “B” so we have to stop. We have yet another new candidate, “BANC”.
- We have hit the end of S so we just output our best candidate, which is “BANC”.
?
LeetCode，?
package Level4;/*** 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.Discuss**/
public class S76 {public static void main(String[] args) {}public String minWindow(String S, String T) {// 因為處理的是字符，所以可以利用ASCII字符來保存int[] needToFind = new int[256]; // 保存T中需要查找字符的個數，該數組一旦初始化完畢就不再改動int[] hasFound = new int[256]; // 保存S中已經找到字符的個數，該數組會動態變化for(int i=0; i<T.length(); i++){ // 初始化needToFind為需要查找字符的個數，needToFind[T.charAt(i)]++; // 如例子中T為ABC，則將會被初始化為：needToFind[65]=1, nTF[66]=2, nTF[67]=3}int count = 0; // 用于檢測第一個符合T的S的字串int minWindowSize = Integer.MAX_VALUE; // 最小窗口大小int start = 0, end = 0; // 窗口的開始喝結束指針String window = ""; // 最小窗口對應的字串for(; end<S.length(); end++){ // 用end來遍歷S字符串if(needToFind[S.charAt(end)] == 0){ // 表示可以忽略的字符，即除了T(ABC)外的所有字符continue;}char c = S.charAt(end);hasFound[c]++; // 找到一個需要找的字符if(hasFound[c] <= needToFind[c]){ // 如果找到的已經超過了需要的，就沒必要繼續增加countcount++;}if(count == T.length()){ // 該窗口中至少包含了Twhile(needToFind[S.charAt(start)] == 0 || // 壓縮窗口，往后移start指針，一種情況是start指針指的都是可忽略的字符hasFound[S.charAt(start)] > needToFind[S.charAt(start)]){ // 另一種情況是已經找到字符的個數超過了需要找的個數，因此可以舍棄掉多余的部分if(hasFound[S.charAt(start)] > needToFind[S.charAt(start)]){hasFound[S.charAt(start)]--; // 舍棄掉多余的部分}start++; // 壓縮窗口}if(end-start+1 < minWindowSize){ // 保存最小窗口minWindowSize = end-start+1;window = S.substring(start, end+1);}}}return window;}
}
?
?
