题解 | #表达式求值#

最小覆盖子串

http://www.nowcoder.com/practice/c466d480d20c4c7c9d322d12ca7955ac

建立一个字典,记录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]
                    
                
        
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-09 12:10
点赞 评论 收藏
分享
叶扰云倾:进度更新,现在阿里云面完3面了,感觉3面答得还行,基本都答上了,自己熟悉的地方也说的比较细致,但感觉面试官有点心不在焉不知道是不是不想要我了,求阿里收留,我直接秒到岗当阿里孝子,学校那边的房子都退租了,下学期都不回学校,全职猛猛实习半年。这种条件还不诱人吗难道 然后现在约到了字节的一面和淘天的复活赛,外加猿辅导。华为笔试完没动静。 美团那边之前投了个base广州的,把我流程卡麻了,应该是不怎么招人,我直接简历挂了,现在进了一个正常的后端流程,还在筛选,不知道还有没有hc。
点赞 评论 收藏
分享
机械打工仔:我来告诉你原因,是因为sobb有在线简历,有些HR为了快会直接先看在线简历,初步感觉不合适就不会找你要详细的了
投了多少份简历才上岸
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-04 18:25
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务