Giả sử chúng ta có hai chuỗi S và T, chúng ta phải tìm chuỗi con W nhỏ nhất của S, sao cho T là một dãy con của W. Nếu không có cửa sổ nào như vậy trong S bao gồm tất cả các ký tự trong T, thì trả về chuỗi trống. Nếu có nhiều cửa sổ như vậy, chúng ta phải trả về cửa sổ có chỉ mục bắt đầu ngoài cùng bên trái.
Vì vậy, nếu đầu vào giống như S ="abcdebdde", T ="bde", thì đầu ra sẽ là "bcde" như nó xảy ra trước "bdde". "deb" không phải là một cửa sổ nhỏ hơn vì các phần tử của T trong cửa sổ phải diễn ra theo thứ tự.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
tidx:=0, tlen:=kích thước của T
-
n:=kích thước của S
-
i:=0, length:=inf, start:=-1
-
trong khi tôi
-
nếu S [i] giống T [tidx] thì -
-
(tăng tidx lên 1)
-
nếu tidx giống với tlen, thì -
-
end:=i + 1
-
(giảm tidx 1)
-
while tidx> =0, do -
-
nếu S [i] giống T [tidx] thì -
-
(giảm tidx 1)
-
-
(giảm i đi 1)
-
-
(tăng tôi lên 1)
-
(tăng tidx lên 1)
-
if end - i
-
length:=end - i
-
start:=i
-
-
-
-
(tăng tôi lên 1)
-
-
nếu bắt đầu không bằng -1, thì -
-
để khởi tạo i:=start, khi tôi
-
ret:=ret + S [i]
-
-
-
trả lại ret
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
#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"));
} Đầu vào
"abcdebdde", "bde"
Đầu ra
"bcde"