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).
Example:
Input: S = "ADOBECODEBANC", T = "ABC" Output: "BANC"Note:
If there is no such window in S that covers all characters in T, return the empty string "".If there is such window, you are guaranteed that there will always be only one unique minimum window in S.
题意：
给定字符串S 和 T， 求S中可以cover T所有元素的子集的最小长度。
Solution1： Two Pointers(sliding window)
1. scan String T, using a map to record each char's frequency
2. use [leftMost to i] to maintain a sliding window, making sure that each char's frequency in such sliding window == that in T
3. if mapS [S.charAt(start)] > mapT [S.charAt(start)] , it signs we can move sliding window
4. how to find the next sliding window? move leftMost, meanwhile, decrement mapS [S.charAt(start)] until we find each frequency in [start to i] == that in T
code
1 class Solution { 2 public String minWindow(String S, String T) { 3 String result = ""; 4 if (S == null || S.length() == 0) return result; 5 int[] mapT = new int[256]; 6 int[] mapS = new int[256]; 7 int count = 0; 8 int leftMost = 0; 9 for(int i = 0; i < T.length(); i++){ 10 mapT[T.charAt(i)] ++; 11 } 12 13 for(int i = 0; i < S.length(); i++){ 14 char s = S.charAt(i); 15 mapS[s]++; 16 if(mapT[s] >= mapS[s]){ 17 count ++; 18 } 19 20 if(count == T.length()){ 21 while(mapS[S.charAt(leftMost)] > mapT[S.charAt(leftMost)]){ 22 if(mapS[S.charAt(leftMost)] > mapT[S.charAt(leftMost)]){ 23 mapS[S.charAt(leftMost)]--; 24 } 25 leftMost ++; 26 } 27 if(result.equals("") || i - leftMost + 1 < result.length()){ 28 result = S.substring(leftMost, i+1); 29 } 30 } 31 } 32 return result; 33 } 34 }
转载于:https://www.cnblogs.com/liuliu5151/p/9070180.html
