C++での最小ウィンドウサブシーケンス

2つの文字列SとTがあるとすると、Sの最小部分文字列Wを見つけて、TがWの部分列になるようにする必要があります。SにTのすべての文字をカバーするウィンドウがない場合は、空の文字列を返します。そのようなウィンドウが複数ある場合は、開始インデックスが一番左にあるウィンドウを返す必要があります。

したがって、入力がS ="abcdebdde"、T ="bde"の場合、出力は"bdde"の前に発生する"bcde"になります。 「deb」は、ウィンドウ内のTの要素が順番に発生する必要があるため、小さいウィンドウではありません。

これを解決するには、次の手順に従います-

• tidx：=0、tlen：=Tのサイズ

• n：=Sのサイズ

• i：=0、長さ：=inf、開始：=-1

• i

  • S[i]がT[tidx]と同じ場合、-

    • （tidxを1増やします）

    • tidxがtlenと同じ場合、-

      • 終了：=i + 1

      • （tidxを1減らします）

      • tidx> =0の場合、実行-

        • S[i]がT[tidx]と同じ場合、-

          • （tidxを1減らします）

        • （iを1減らします）

      • （iを1増やします）

      • （tidxを1増やします）

      • end --i

        • 長さ：=終了-i

        • start：=i

  • （iを1増やします）

• startが-1に等しくない場合、-

  • 初期化i：=startの場合、i

    • ret：=ret + S [i]

• retを返す

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   string minWindow(string S, string T) {
      int tidx = 0;
      int tlen = T.size();
      int n = S.size();
      int i = 0;
      int length = INT_MAX;
      int start = -1;
      string ret;
      while (i < n) {
         if (S[i] == T[tidx]) {
            tidx++;
            if (tidx == tlen) {
               int end = i + 1;
               tidx--;
               while (tidx >= 0) {
                  if (S[i] == T[tidx]) {
                     tidx--;
                  }
                  i--;
               }
               i++;
               tidx++;
               if (end - i < length) {
                  length = end - i;
                  start = i;
               }
            }
         }
         i++;
      }
      if (start != -1)
      for (int i = start; i < start + length; i++)
      ret += S[i];
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.minWindow("abcdebdde", "bde"));
}

入力

"abcdebdde", "bde"

出力

"bcde"