[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).

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

 class Solution {

     public String minWindow(String S, String T) {

         String result = "";

         if (S == null || S.length() == 0) return result;

         int[] mapT = new int[256];

         int[] mapS = new int[256];

         int count = 0;

         int leftMost = 0;

         for(int i = 0; i < T.length(); i++){

             mapT[T.charAt(i)] ++;

         }

          for(int i = 0; i < S.length(); i++){

              char s = S.charAt(i);

              mapS[s]++;

              if(mapT[s] >= mapS[s]){

                  count ++;

              }

              if(count == T.length()){

                  while(mapS[S.charAt(leftMost)] > mapT[S.charAt(leftMost)]){

                      if(mapS[S.charAt(leftMost)] > mapT[S.charAt(leftMost)]){

                          mapS[S.charAt(leftMost)]--;

                      }

                      leftMost ++;

                  }

                   if(result.equals("") || i - leftMost + 1 < result.length()){

                      result =  S.substring(leftMost, i+1);

                  }

              }

          }

       return result;

     }

 }

二刷：

对于出现在S但不出现在T的那些“配角” character的处理，

最好的方式是，边扫S边用map将其频率一并记上。

这样，在判断 while(mapS[S.charAt(leftMost)] > mapT[S.charAt(leftMost)]) 这个逻辑的时候，

这些“配角”character会因为只出现在S但不出现在T

而直接被left++给做掉

 class Solution {

     public String minWindow(String s, String t) {

         String result = "";

         if(s == null || s.length() == 0 || s.length() < t.length()) return result;

         int [] mapT = new int [128];

         for(Character c : t.toCharArray()){

             mapT[c]++;

         }

         int left = 0;

         int count = t.length();

         int[] mapS = new int[128];

         for(int i = 0; i < s.length(); i++){

             char c = s.charAt(i);

                 mapS[c] ++ ;

                 if(mapT[c] >= mapS[c]){

                     count --;

             }

             if(count == 0){

                 while(mapS[s.charAt(left)] > mapT[s.charAt(left)]){

                     mapS[s.charAt(left)] --;

                     left++;

                 }

                if (result.equals("") || i - start + 1 < result.length()) {

                     result = s.substring(start, i + 1);

                 }

             }

         }

      return result;

     }

 }

巴特西

[leetcode]76. Minimum Window Substring最小字符串窗口

最新文章

热门文章