Problem 76: Minimum Window Substring

https://leetcode.com/problems/minimum-window-substring/

思路

• 这道题非常地经典，甚至衍生出了一个模板，可以处理类似的所有 substring 类的题目。

  https://discuss.leetcode.com/topic/30941/here-is-a-10-line-template-that-can-solve-most-substring-problems/44

• 这道题的思路就是用一个 hashmap (这里用的是 128 长度的 array，间接起到了 map 的作用) 来存储 pattern 元素；用 count 来判断当前的 window 里是否包含了这个 pattern

• 这里的处理问题的顺序是：先移动 j 尾巴，再移动 i head。

复杂度

• Time: O(n)

public class Solution {
    public String minWindow(String s, String t) {
        int[] map = new int[128];
        for (char c : t.toCharArray()) {
            map[c]++;
        }

        int i = 0, j = 0, start = 0;
        int count = t.length(), minLen = Integer.MAX_VALUE;
        while (j < s.length()) {
            if (map[s.charAt(j++)]-- > 0) count--;
            while (count == 0) { // valid
                if (j - i < minLen) {
                    minLen = j - i;
                    start = i;
                }
                if (map[s.charAt(i++)]++ == 0) count++; 
            }
        }

        return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
    }
}

易错点

1. 关键语句的解读

   if (map[s.charAt(j++)]-- > 0)

   这里实际上是，

   if (map[s.charAt(j)] > 0) {...}
   map[s.charAt(j)]--;
   j++;