C ++中的最小窗口子序列

假设我们有两个字符串S和T，我们必须找到S的最小子字符串W，以便T是W的子序列。如果S中没有覆盖T中所有字符的窗口，则返回空字符串。如果有多个这样的窗口，我们必须返回最左侧的起始索引的窗口。

因此，如果输入类似于S =“ abcdebdde”，T =“ bde”，则输出将为“ bcde”，因为它出现在“ bdde”之前。“ deb”不是一个较小的窗口，因为窗口中T的元素必须按顺序出现。

为了解决这个问题，我们将遵循以下步骤-

• tidx：= 0，tlen：= T的大小

• n：= S的大小

• i：= 0，长度：= inf，开始：= -1

• 当我<n时，-

• （将tidx增加1）

• 如果tidx与tlen相同，则-

• 长度：=结束-我

• 开始：=我

• 如果S [i]与T [tidx]相同，则-

• （将i减1）

• （将tidx减少1）

• 结束：= i + 1

• （将tidx减少1）

• 当tidx> = 0时，执行-

• （将i增加1）

• （将tidx增加1）

• 如果结尾-i <长度，则-

• 如果S [i]与T [tidx]相同，则-

• （将i增加1）

• 如果start不等于-1，则-

• ret：= ret + S [i]

• 对于初始化i：=开始，当i <开始+长度，更新（将i增加1）时，执行-

• 返回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"