アルゴリズム

[LeetCode76]最小ウィンドウ部分文字列



Minimum Window Substring



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

例：



Input: S = 'ADOBECODEBANC', T = 'ABC' Output: 'BANC'

注意：

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

解決

  1. 文字の出現頻度についてhashtableここでの文字は実際にはASCIIコードの最初の128文字にすぎないので、int[128]を使用してください。
  2. 最初の統計T string、int[128]各文字の数が上部に記録されます。
  3. O（n）時間を使用するには、スライディングウィンドウのアイデアを使用します。次に、このウィンドウを定義します。ウィンドウの左から右の境界線の文字にはT stringのすべての文字が含まれ、左の境界線が再び右に移動してはなりません。
  4. 同時に、1つを定義しますcounter記録するにはS string検出された文字数T string文字の場合counter = s.lengthすべての文字が検出されたことを示しますが、余分な文字が含まれる場合があります。最小のセットではありません。この時点で、左の境界線を移動する必要があります。具体的なロジックは次のとおりです。

  • カウンターを定義します。初期化距離はs.length、in S stringウィンドウをスライドするとき（左右の境界線は最初は0です）：
    1）右の境界線を右にスライドするとき、文字を追加するたびに、それがT string中程度の文字であり、出現頻度がT string文字の頻度を超えない場合counter - 1。
    2）左の境界線を右にスライドするとき、T string中程度の文字で、出現頻度がT string文字の頻度を超えない場合は、1文字ずつ削除しますcounter + 1。



  • 右の境界線を判断する ：
    1）この位置の値> 0が、この位置がT string中程度の文字であり、ウィンドウ内の数が十分でないことを示している場合。counter --。
    2）この位置の値<= 0の場合、この位置は次のとおりです。操作しないでください。
    *はT stringの文字ではありません。
    *はいT stringボックス内の文字ですが、ウィンドウ内の文字が大きすぎて負になりません。

  • 現在のカウンターは0です 、説明ウィンドウにはすべての文字が含まれていますが、さらに多くの文字が含まれている可能性があります。プロセスで左の境界線を移動してみてくださいupdate counter Once counter != 0次に、左の境界線の移動を停止します。
    1）もし 左ボーダー in int[128]対応する位置の値== 0、この文字がコレクションに必要な文字であり（そうでない場合、この位置の値は負である必要があります）、数値が適切であることを示しますcounter ++ （削除されるため、update counter）
    2）int [128] ++1の対応する位置の値そして、左の境界線を右に移動します。

時間：O（n）、スペースO（1）

コード

class Solution { public String minWindow(String s, String t) { int sLen = s.length () int tLen = t.length () // S is shorter than T, can never find such substring if (sLen 0) { count -- } tracker [s.charAt (right)] -- right ++ // move right pointer // found all characters, try to move left pointer while (count == 0) { // update the min substring head and length if (right - left