[LeetCode]题解（python）：076-Minimum Window Substring

题目来源：

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

题意分析：

　　给定两个字符串S和T。在S中找到最短的一个子字符串使得他包括所有的T。比如：S = "ADOBECODEBANC"，T = "ABC"，那么返回"BANC"。要求时间复杂度O（n）。

题目分析：

　　利用字典记录T中每个字符出现的次数。①在S中找到最开始包括所有T中字符的一个结果，并且使得这个结果的第一个字符是T中的。也就是先找到一个满足答案。上题例子就是找到了"ADOBEC"，更新目前的答案，使得当前答案中没有更短的字符串满足，也就是说，如果上题找到的满足是"AADOBEC"的话，要更新为"ADOBEC"，记录当前的长度和当前答案。②然后去掉第一个字符，然后往后更新，直到再次找到满足的答案，接着更新答案，比较和第一个的长度，如果是比第一个更短，更新长度和答案。③重复②的动作，直到找到了S中的末尾。

代码（Python）：

 1 class Solution(object):
 2     def minWindow(self, s, t):
 3         """
 4         :type s: str
 5         :type t: str
 6         :rtype: str
 7         """
 8         m,n = len(s),len(t)
 9         if m == 0 or n == 0:
10             return ""
11         dn,dm = {},{}
12         for i in t:
13             if i in dn:
14                 dn[i] += 1
15             else:
16                 dn[i] = 1
17         i,first,last,mark,mark1 = 0,0,0,True,False
18         count = 0
19         while i < m:
20             if s[i] in dn:
21                 if mark:
22                     first,mark = i,False
23                 if s[i] in dm:
24                     dm[s[i]]+=1
25                 else:
26                     dm[s[i]] = 1
27                 if dm[s[i]] <= dn[s[i]]:
28                     count += 1
29                 if count == n:
30                     mark1 = True
31                     last = i;break
32             i += 1
33         if not mark1:
34             return ""
35         t = first
36         while t < m:
37             if s[t] in dm:
38                 if dm[s[t]] == dn[s[t]]:
39                     first = t;break
40                 else:
41                     dm[s[t]] -= 1
42             t += 1
43         ans = [first,last]
44         while True:
45             j,k = first + 1,last + 1
46             tmp = s[first]
47             while j < m:
48                 if s[j] in dn:
49                     if dm[s[j]] <= dn[s[j]]:
50                         first = j;break
51                     else:
52                         dm[s[j]] -= 1
53                 j += 1
54             while k < m:
55                 if s[k] == tmp:
56                     last,t = k,first
57                     while t < m:
58                         if s[t] in dm:
59                             if dm[s[t]] == dn[s[t]]:
60                                 first = t;break
61                             else:
62                                 dm[s[t]] -= 1
63                         t += 1
64                     if last - first <= ans[1] - ans[0]:
65                         ans = [first,last]
66                     break
67                 if s[k] in dm:
68                     dm[s[k]] += 1
69                 k += 1
70             if k == m:
71                 break
72         return s[ans[0]:ans[1]+1]
73

View Code

转载请注明出处：http://www.cnblogs.com/chruny/p/5088501.html