LeetCode76.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.

思路：

题目要求的时间复杂度为O(n)，意味着选定窗口大小，依次遍历字符串的暴力方法（时间复杂度为O(n^2)）不合适。

联想到“有序数组和中为S的两个数”问题的解法，可以尝试用指针移动的方式来遍历字符串，以达到O(n)的时间复杂度。

基本的思路是右指针从左向右遍历S，对每一个右指针问题，求可能的最短窗口（用左指针从左向右的遍历实现）。为了判断窗口的合法性，需要一个字典，存储目标字符串T中的元素在窗口中是否出现。

python的具体实现代码如下：

 1 class Solution(object):
 2     def minWindow(self, s, t):
 3         if not s or not t:
 4             return ""
 5         need = {}
 6         for char in t:
 7             if char not in need:
 8                 need[char] = 1
 9             else:
10                 need[char] += 1
11         missing = len(t)
12         min_left = 0
13         min_len = len(s) + 1
14         left = 0
15         for right, char in enumerate(s):
16             if char in need:
17                 need[char] -= 1
18                 if need[char] >= 0:
19                     missing -= 1
20                 while missing == 0:
21                     if right - left + 1 < min_len:
22                         min_left, min_len = left, (right - left + 1)
23                     if s[left] in need:
24                         need[s[left]] += 1
25                         if need[s[left]] > 0:
26                             missing += 1
27                     left += 1
28         if min_len > len(s):
29             return ""
30         return s[min_left: min_left + min_len]

在leetcode上显示运行时间快过99%的提交方案