リートコード

leetcode76。最小ウィンドウ部分文字列



Leetcode 76 Minimum Window Substring



問題の説明

文字列Sと文字列Tが与えられた場合、複雑さO（n）のTのすべての文字を含むSの最小ウィンドウを見つけます。
例：

入力：S =“ ADOBECODEBANC”、T =“ ABC”
出力：「BANC」
注意：



  • Tのすべての文字をカバーするウィンドウがSにない場合は、空の文字列「」を返します。
  • そのようなウィンドウがある場合、Sには常に1つの一意の最小ウィンドウのみが存在することが保証されます。

問題分析

この問題は一連の部分文字列処理であり、スライディングウィンドウを解決できます。文字列sと文字列tの場合、sに含まれる文字の最小文字列を検索します。ウィンドウには左右の2つのポインタが含まれているため、文字列tを調べるかどうかに関係なく、各文字を繰り返す必要があります。ここでは、文字列tが重要かどうかを確認するための手順を実行し、マップを使用して解決します。統計t各文字の数が表示されます。文字列tに対応するマップのトラバーサルが値-1、-1の値をマッピングする場合、変更も0より大きい場合は、文字列t内の文字が、カウンターcnt ++を使用して、ウィンドウにすでに含まれているtを計算したことを示します。キャラクター。 cnt == t.size（）の場合、ウィンドウは文字tに完全に含まれています。ウィンドウサイズを更新します。この時点で、より小さなウィンドウを見つけるために、ウィンドウを狭めるために、左のポインタを右に向けます。 0より大きい場合、左++マッピング値と呼ばれる文字固有の操作。これは、tの文字がCNT-であることを示します。文字がtの意味の範囲内に残されている場合、0に等しくなります。

コード

class Solution { public: string minWindow(string s, string t) { string res ='' int minLen = INT_MAX if(s.size() == 0 ||t.size() ==0 ) return '' map m for (int i = 0 i right-left+1){ minLen = right-left+1 res = s.substr(left,minLen) } if(++m[s[left]]>0) cnt-- left++ } } return res } }