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

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

原问题链接：https://leetcode.com/problems/minimum-window-substring/

 

问题分析

　　这个问题相对比较复杂，主要是对于给定窗口的值和目标值之间的比较匹配和最小窗口的判断。这里结合这两个点来讨论。

　　首先一个，对于给定的一个源串来说，我怎么知道其中的某一段就包含了目标串里所有的字符呢？尤其是在一个串里还可能有多次重复的元素。一个基本的思路是，我们首先遍历目标串，将它里面每个字符和字符出现的次数都映射保存到一个map里。这样就有了一个保存和比较的基础。对于源串来说，每遍历遇到一个元素的时候就要和目标串建立的map进行比较。可是怎么确保源串的部分正好就涵盖了目标串的所有字符呢？如果每碰到一个就对原来的map里对应的元素减一的话，这样还是不能保证恰好都涵盖了所有的。一种思路是我们用一个变量count来记录目标串的长度。每次在遍历源串的时候，碰到的字符在目标串里存在的，而且在源串里出现的次数小于等于目标串里出现的次数，我们就对count加一。这样直到最后count的值和目标串的长度相等。我们就肯定可以确定，前面这一段是已经涵盖目标串了。

　　解决了第一个问题之后，下一个问题就是怎么找到最小的窗口呢？这个时候我们就需要从源串的开头去再次遍历这个串。在碰到一个存在于目标串中的元素时，这个位置才可能是窗口的开头。这样就跳过了一些在目标串中不存在的元素。但是这样做还是不够充分的。还有一种情况就是我们遍历过的某一段字符串它里面有些在目标串里也存在的字符出现的次数比目标串里出现的次数还要多。这个时候对于这些存在于源串中但是出现次数更多的情况，我们是可以继续将字符串的位置往后面移的，因为这样肯定保证了串包含了给定的目标串内容，同时也尽量缩小了串的长度。

　　按照这个思路，我们在具体的实现里用了两个map，一个用来保存目标串t里所有字符和出现的次数。另外一个用来记录遍历源串s时在目标串中出现的字符和次数。我们一边遍历s的时候一边记录符合条件的元素的个数。在发现符合条件的字符串长度达到给定长度时则从头开始进行最小窗口的判断。每次比较后将最小窗口的开始和结束位置保存下来。还有一个情况就是在源串里根本就不可能包含有目标串所有的字符，这里具体的实现就是通过判断位置元素l是否为-1。因为一旦有符合条件的串，l必然参加比较，它也将会被赋值。详细代码实现如下：

 

public class Solution {
    public String minWindow(String s, String t) {
        if(s.isEmpty() || t.isEmpty()) return "";
        Map<Character, Integer> itemsFound = new HashMap<>();
        Map<Character, Integer> toBeFound = new HashMap<>();
        int count = 0, minLen = Integer.MAX_VALUE, l = -1, r = -1;
        for(int i = 0; i < t.length(); i++) {
            char c = t.charAt(i);
            if(toBeFound.containsKey(c))
                toBeFound.put(c, toBeFound.get(c) + 1);
            else toBeFound.put(c, 1);
        }
        for(int start = 0, end = 0; end < s.length(); end++) {
            char e = s.charAt(end);
            if(!toBeFound.containsKey(e)) continue;
            if(itemsFound.containsKey(e))
                itemsFound.put(e, itemsFound.get(e) + 1);
            else itemsFound.put(e, 1);
            if(itemsFound.get(e) <= toBeFound.get(e)) count++;
            if(count == t.length()) {
                char ch = s.charAt(start);
                while(!toBeFound.containsKey(ch) || itemsFound.get(ch) > toBeFound.get(ch)) {
                    if(toBeFound.containsKey(ch) && itemsFound.get(ch) > toBeFound.get(ch)) 
                        itemsFound.put(ch, itemsFound.get(ch) - 1);
                    start++;
                    ch = s.charAt(start);
                }
                if(end - start < minLen) {
                    minLen = end - start;
                    l = start;
                    r = end;
                }
            }
        }
        return l == -1 ? "" : s.substring(l, r + 1);
    }
}

 　这个方法实现的时间复杂度为O(N)。在实际执行的结果里我们会发现它的效率并不是很高。因为这里用的map保存的数据类型和字符串里的char类型等需要进行类型的boxing和unboxing，它在很大程度上拖累了性能。在有的实现里将两个串首先转换成纯字符数组然后再进行统计比较，这样可以极大的提高系统执行的效率。

 

参考材料

http://articles.leetcode.com/finding-minimum-window-in-s-which/