Leetcode作題日記:76.最小カバーサブストリング(PYTHON)

1つの文字列Sと1つの文字列Tを指定し、Sの中でTのすべての文字を含む最小サブ列を見つけてください.
例:
入力:S=“ADOBECODEBANC”,T=“ABC”出力:“BANC”
説明:

   S         ，        ""。
   S         ，           。

最初のコード:sを繰り返し、適切なサブストリングを見つけます.

	t1=[]
        for i in t:
            t1.append(i)
            if i not in s or len(s)<len(t):
                return ''
        used=t1[:]#        t    
        ans=''
        ans1=[]
        for i in range(len(s)):
            if s[i] in t: #         
                j=0
                while used:# used  ，               
                    if i+j==len(s):
                        break
                    ans=ans+s[i+j] #      
                    if ans1 and len(ans)>len(ans1[0]): #              
                        break
                    if s[i+j] in t and s[i+j] in used: #  t    ，used  
                        used.remove(s[i+j])
                    j=j+1    
                if (not ans1 or (ans1 and len(ans)<=len(ans1[0]))) and not used:
                    if ans1:ans1.pop()
                    ans1.append(ans)
            i=i+1
            ans=''
            used=t1[:]
        if ans1:
            return ans1[0]
        else:
            return ''

やはり最後の例でタイムアウトして2回目のコード:weizhiでsの中でtに属するアルファベットの座標を記録します.つまり、答えはこれらの座標の中で、最小列はtの中のアルファベットで始まる必要があるので、weizhiリストで遍歴します.usedリストが空であれば、tの中のアルファベットが1回使用されたことを示し、サブ列を得て、サブ列の長さと座標をリストに加えます.最後に最も短いサブストリングの長さと座標を見つけて、戻ればいいです.

	t1=[]
        for i in t:
            t1.append(i)
            if i not in s or len(s)<len(t):
                return ''
   
        used=t1[:]
        weizhi=[]
        for i in range(len(s)):
            if s[i] in t:
                weizhi.append(i)
        i=0
        weizhicha=[]
        answeizhi=[]
        while i < len(weizhi):
            j=1
            used=t1[:]
            used.remove(s[weizhi[i]])
            while used and i+j<len(weizhi):
                if s[weizhi[i+j]] in used :
                    used.remove(s[weizhi[i+j]])
                j=j+1
                if j==len(weizhi):
                    break
            if not used:
                weizhicha.append(weizhi[i+j-1]-weizhi[i])
                answeizhi.append([weizhi[i],weizhi[i+j-1]])
            i=i+1
        if weizhicha:    
            index=weizhicha.index(min(weizhicha))
            i=answeizhi[index][0]
            j=answeizhi[index][1]
            return s[i:j+1]
        else:
            return ''

内部エラー???何の鬼だ,2回更新したのか,やはりタイムアウトした.3回目のコード:まずハッシュテーブルTを確立し、t内のすべてのアルファベットとその個数を格納する.次に、2つのポインタl,rを用いて、まずrを移動し、[l,r]内の文字列が適切に要求を満たすと、その文字列の内部にも条件を満たす文字のサブ列がある可能性があり、次にlを移動し、条件を満たす文字の文字列を見つけ、その後、2回目の反復を開始し、r...を移動する.要求を満たす文字列をカウントするにはcountを用い,ハッシュテーブルTはcountの減算条件とする.例は理解しやすい:s=abcbcd,t=bc,第1ラウンド反復,先にrを移動し,abcを得,移動lでbcが満足し,さらにlを移動し,cが満足しないことを得,移動lを脱退し,次のサイクル移動rを開始する

 	if len(s)<len(t):
            return ''
        T={}
        for i in t:
            if i in t:
                if i in T:
                    T[i]+=1
                else:
                    T[i]=1
        l=0
        r=0
        count=0
        ans=''
        minl=len(s)+1 #        len(s)+1，    s,t   
        while r<len(s):
            if s[r] in T:
                T[s[r]]-=1
                if T[s[r]]>=0:#       ， <0，       
                    count+=1
                while count==len(t): #      ，r    ，      l
                    if (r-l+1)<minl: #          
                        ans=s[l:r+1]
                        minl=r-l+1 #      
                    if s[l] in T: #  l    ，s[l]            
                        T[s[l]]+=1 
                        if T[s[l]]>0: #                ，count-1    
                            count-=1
                    l=l+1 #    l，       ，       
            r=r+1
        return ans             

96 ms、71%