Giả sử chúng ta có hai chuỗi S và T, chúng ta phải tìm xâu con W tối thiểu 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 trong S bao phủ tất cả ký tự trong T, trả về chuỗi rỗng. Nếu có nhiều cửa sổ như vậy, chúng ta phải trả về cái có chỉ số bắt đầu bên trái nhất.
Vì vậy, nếu đầu vào là S = "abcdebdde", T = "bde", đầu ra sẽ là "bcde" vì nó xuất hiện trước "bdde". "deb" không phải cửa sổ nhỏ hơn vì các phần tử của T trong cửa sổ phải xuất hiện theo thứ tự.
Để giải quyết, chúng ta sẽ làm theo các bước:
tidx := 0, tlen := kích thước T
n := kích thước S
i := 0, length := inf, start := -1
Khi i < n, làm:
nếu S[i] giống T[tidx], thì:
(tăng tidx lên 1)
nếu tidx giống tlen, thì:
end := i + 1
(giảm tidx xuống 1)
Khi tidx >= 0, làm:
nếu S[i] giống T[tidx], thì:
(giảm tidx xuống 1)
(giảm i xuống 1)
(tăng i lên 1)
(tăng tidx lên 1)
nếu end - i < length, thì:
length := end - i
start := i
(tăng i lên 1)
nếu start không bằng -1, thì:
Khởi tạo i := start, khi i < start + length, cập nhật (tăng i lên 1), làm:
ret := ret + S[i]
Trả về ret
Hãy xem 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"