数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法律研究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，length := inf，start := -1
当 i < n 时，执行以下操作：
如果 S[i] 与 T[tidx] 相同，则：
(将 tidx 加 1)
如果 tidx 与 tlen 相同，则：
end := i + 1
(将 tidx 减 1)
当 tidx >= 0 时，执行以下操作：
如果 S[i] 与 T[tidx] 相同，则：
(将 tidx 减 1)
(将 i 减 1)
(将 i 加 1)
(将 tidx 加 1)
如果 end - i < length，则：
length := end - i
start := i
(将 i 加 1)
如果 start 不等于 -1，则：
初始化 i := start，当 i < start + length 时，更新 (将 i 加 1)，执行以下操作：
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"
更新于: 2020-07-11
908 次浏览
广告