我打算不定期地整理一下Stefan Pochmann的代码。这位大神的“上帝之手”将告诉你， 什么代码可以体现编程的艺术。
最小覆盖子串
给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串。
示例：
输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"
说明：
- 如果 S 中不存这样的子串，则返回空字符串 ""。
- 如果 S 中存在这样的子串，我们保证它是唯一的答案。
解题思路
详见官方答案。简单来说，在S串中维持一个滑窗，先让滑窗左界不动，右界右滑直到覆盖全部T串字符，然后左界右滑直到刚好不能覆盖T，这时将出现局部最优解。局部最优解与全局最优解比较，较短的为全局最优。上述步骤循环，直到滑窗滑完S串。
常规写法(28行）
def minWindow(self, s, t):
"""
:type s: str
:type t: str
:rtype: str
"""
ls, lt = len(s), len(t)
if ls < lt or lt == 0:
return ""
left, right = 0, 0 #滑窗界
begin, end = None, None # 全局最优窗
l_min_window = float('inf') # 全局最优值
dic_t = {} # 记录T串的字符
for i in t:
dic_t[i] = dic_t.setdefault(i, 0) + 1
required = len(dic_t.keys()) # 检查滑窗是否有效
formed = 0 # 当下满足条件的字符
dic_window = {}
while right < ls:
cur = s[right]
dic_window[cur] = dic_window.get(cur, 0) + 1
if cur in dic_t and dic_window[cur] == dic_t[cur]:
formed += 1
while formed == required and left <= right:
ch = s[left]
if right - left + 1 < l_min_window:
l_min_window = right - left + 1
begin, end = left, right
dic_window[ch] -= 1
if ch in dic_t and dic_window[ch] < dic_t[ch]:
formed -= 1
left += 1
right += 1
return "" if l_min_window == float('inf') else s[begin: end + 1]
上帝之手(12行)
def minWindow(self, s, t):
need, missing = collections.Counter(t), len(t)
i = I = J = 0
for j, c in enumerate(s, 1):
missing -= need[c] > 0
need[c] -= 1
if not missing:
while i < j and need[s[i]] < 0:
need[s[i]] += 1
i += 1
if not J or j - i <= J - I:
I, J = i, j
return s[I:J]
Trick1：使用collections.Counter，高效实现dict_t的功能，而且不出现的字符也可以直接使用；
Trick2：need[c] > 0逻辑值作01值；
Trick3：不用控制“T串的某个字符多次出现在S串，被减多了”的情况。这个技巧节省代码最多，思考量也是最多。
细节1：enumerate的第二个参数是1，如果s[0]是t中字符也不要紧，need[s[i]] += 1会把s[0]算上。
细节2：返回值是s[I:J]而不是s[I:J+1]，这是因为j从1开始滑动。
细节3：如果没匹配到s中的串，s[I:J]就是s[0:0]，返回空串，符合题意要求。
细节4：IJ的更新不在while循环中，可以让程序加速。因为IJ的更新只有在“排除了所有无关字符”后才有意义。
细节5：不必担心i增大时无关字符（不出现在T中的字符）的干扰，因为s[i]如果是无关字符，左界没滑过时为负数，滑过后变为0，不会干扰while循环。
网友评论