Leetcode 76. 最小カバーサブ列minimum window substring-スライドウィンドウ+欲張りポリシー
https://leetcode-cn.com/probl...
問題を解く構想.
lおよびrは、現在のターゲット列の左下および右下である.
r絶えず前進する.
l現在のアルファベットが保持する必要がないことを保証するときに前進する(このアルファベットがターゲット文字列にないか、このアルファベットの現在の数が要求を超えていることを指す必要はありません).これは貪欲な戦略です.
cntはターゲットアルファベットがどれだけ必要かを統計した.
nはcntの中のアルファベットでいくつかの数が満たされています.
ansは最終的な答えだ
コード#コード#
私のブログへようこそ:https://codeplot.top/私のブログのブラシの分類:https://codeplot.top/categories/%E5%88%B7%E9%A2%98/
問題を解く構想.
lおよびrは、現在のターゲット列の左下および右下である.
r絶えず前進する.
l現在のアルファベットが保持する必要がないことを保証するときに前進する(このアルファベットがターゲット文字列にないか、このアルファベットの現在の数が要求を超えていることを指す必要はありません).これは貪欲な戦略です.
cntはターゲットアルファベットがどれだけ必要かを統計した.
nはcntの中のアルファベットでいくつかの数が満たされています.
ansは最終的な答えだ
コード#コード#
class Solution:
def minWindow(self, s: str, t: str) -> str:
import collections
cnt = collections.Counter(t)
ans = ''
n = 0 # t
l = 0
for r, ch in enumerate(s):
if ch not in cnt:
continue
cnt[ch] -= 1
if cnt[ch] == 0:
n += 1
while s[l] not in cnt or cnt[s[l]] < 0: # l , l
if s[l] in cnt: cnt[s[l]] += 1
l += 1
if n == len(cnt):
if not ans or len(ans) > r - l + 1:
ans = s[l: r+1]
return ans
私のブログへようこそ:https://codeplot.top/私のブログのブラシの分類:https://codeplot.top/categories/%E5%88%B7%E9%A2%98/