大学IT网 - 最懂大学生的IT学习网站! QQ资料交流群:367606806
当前位置:大学IT网 > Java技巧 > LeetCode: Minimum Window Subst

LeetCode: Minimum Window Subst

关键词:MinimumLeetCodeSubstringWin  阅读(1065) 赞(12)

[摘要]本文是对LeetCode: Minimum Window Substring的讲解,对学习Java编程技术有所帮助,与大家分享。
 /**
  * 
  */
 package solution;
 
 import java.util.HashMap;
 
 /**
  * @author whh
  * 
  *         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.
  */
 public class MinimumWindowSubstring {
 
     /**
      * @param args
      */
     public static void main(String[] args) {
         MinimumWindowSubstring mws = new MinimumWindowSubstring();
         String S = "aabbDEE", T = "aabbDEE";
         System.out.println(mws.minWindow(S, T));
     }
 
     /**
      * @param S
      * @param T
      * @return
      */
     public String minWindow(String S, String T) {
 
         HashMap<Character, Integer> hasFound = new HashMap<Character, Integer>();
         HashMap<Character, Integer> needToFind = new HashMap<Character, Integer>();
 
         for (int i = 0; i < T.length(); i++) {
             hasFound.put(T.charAt(i), 0);
 
             if (needToFind.containsKey(T.charAt(i))) {
                 needToFind.put(T.charAt(i), needToFind.get(T.charAt(i)) + 1);
             } else {
                 needToFind.put(T.charAt(i), 1);
             }
         }
 
         int begin = 0;
         int minWindowSize = S.length();
         String retString = "";
 
         int count = 0;
 
         for (int end = 0; end < S.length(); end++) {
             Character end_c = S.charAt(end);
             if (needToFind.containsKey(end_c)) {
                 hasFound.put(end_c, hasFound.get(end_c) + 1);
                 if (hasFound.get(end_c) <= needToFind.get(end_c)) {
                     count++;
                 }
                 if (count == T.length()) {
                     while ((!needToFind.containsKey(S.charAt(begin)))
                             || (hasFound.get(S.charAt(begin)) > needToFind
                                     .get(S.charAt(begin)))) {
 
                         if (needToFind.containsKey(S.charAt(begin))) {
                             hasFound.put(S.charAt(begin),
                                     hasFound.get(S.charAt(begin)) - 1);
                         }
 
                         begin++;
                     }
 
                     if ((end - begin + 1) <= minWindowSize) {
                         minWindowSize = end - begin + 1;
                         retString = S.substring(begin, end + 1);
                     }
                 }
             }
         }
 
         return retString;
     }
 
 }


相关评论