首页 > Windows开发 > 详细

[Leetcode] Minimum Window Substring

时间:2015-09-30 11:02:54      阅读:230      评论:0      收藏:0      [点我收藏+]

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 empty string "".

If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

 

  1. hashmap to store target string (T)’s information, character -> occurrences

  2. left pointer points to the window’s left

  3. right pointer points to the window’s right

  4. min(int) to store the minimum window’s length so far

  5. start(int) to mark the start index of the minimum window so far

  6. and a count(int), when the count equals the size of target string -> there is a candidate window

 

while loop end condition is when right == S.length()

if(s.charAt(right)) is in the map, then the according value -1, and if the value == 0, count++

while(count == map.size())

  1. calculate the current window length, update the min and start if necessary

  2. check if map contains charAt(left), if yes the according value +1, and if the value >0, count--

  3. move left to the next



edgecase

s == null? “”

t == null?  “”


Notice:

    1. count equals to map.size, not T.length
    2. typo
          public String minWindow(String s, String t){
              if(s == null || t == null) return "";
              HashMap<Character, Integer> map = new HashMap<Character, Integer>();
              int left = 0, right = 0, min = Integer.MAX_VALUE, start = -1, count = 0, n = s.length();
              
              for(int i = 0; i < t.length(); i++){
                  char c = t.charAt(i);
                  if(map.containsKey(c)){
                      map.put(c, map.get(c)+1);
                  }
                  else{
                      map.put(c, 1);
                  }
              }
           
              while(right < n){
                  char c = s.charAt(right);
                  if(!map.containsKey(c)){
                      right++;
                       continue;
                  }
                  map.put(c, map.get(c)-1);
                  if(map.get(c) == 0) count++;
                  while(count == map.size()){
                      int curLen = right-left+1;
                      if(curLen < min){
                          start = left;
                          min = curLen;
                      }
                      if(map.containsKey(s.charAt(left))){
                          map.put(s.charAt(left), map.get(s.charAt(left))+1);
                          if(map.get(s.charAt(left)) >0) count--;
                      }
                      left++;
                  }
                  right++;
              }
              if(start == -1) return "";
              return s.substring(start, start+min);
          }

       

[Leetcode] Minimum Window Substring

原文:http://www.cnblogs.com/momoco/p/4848431.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!