题解 | #表达式求值#

建立一个字典，记录T中字符出现的次数。然后放大(滑动)窗口，当字典里的次数全都小于0的时候，进行窗口缩小;直到缩小的出现字典某个字符大于0的情况，此时，继续放大窗口。

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param S string字符串 
# @param T string字符串 
# @return string字符串
#
class Solution:
    def minWindow(self , S: str, T: str) -> str:
        # write code here
        start = 0
        end = 0
        hash_dic = dict()
        match = len(T)
        res_start = -1
        res_end = -1
		#初始化HASH
        for i in range(match):
            if T[i] not in hash_dic:
                hash_dic[T[i]] = 1
            else:
                hash_dic[T[i]] += 1
        #放大窗口
		while end < len(S):
            if S[end] in hash_dic:
                hash_dic[S[end]] -= 1
                if hash_dic[S[end]] >=0:
                    match -= 1
			#当匹配HASH中的所有数都小于等于0，开始缩小窗口
            while match == 0:
            	#缩小的过程，记录最优长度
                if (res_end==-1 and res_start==-1) or (end - start + 1 < res_end - res_start + 1):
                    res_start = start
                    res_end = end
                if S[start] in hash_dic:
                    hash_dic[S[start]] += 1
                    if hash_dic[S[start]] > 0:
                        match += 1
                start += 1
            end += 1
        if res_start == -1 or res_end == -1:
            return ""
        return S[res_start:res_end+1]