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"