สมมติว่าเรามีสตริงย่อย S และ T สองสตริง เราต้องหาสตริงย่อยขั้นต่ำ W ของ S เพื่อให้ T เป็นผลสืบเนื่องของ W หากไม่มีหน้าต่างดังกล่าวใน S ที่ครอบคลุมอักขระทั้งหมดใน T ให้ส่งคืนสตริงว่าง หากมีหลายหน้าต่างดังกล่าว เราต้องคืนค่าหน้าต่างที่มีดัชนีเริ่มต้นด้านซ้ายสุด
ดังนั้น หากอินพุตเป็น S ="abcdebdde", T ="bde" เอาต์พุตจะเป็น "bcde" เนื่องจากเกิดขึ้นก่อน "bdde" "deb" ไม่ใช่หน้าต่างที่เล็กกว่าเพราะองค์ประกอบของ T ในหน้าต่างต้องเกิดขึ้นตามลำดับ
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
tidx :=0, tlen :=ขนาดของ T
-
n :=ขนาด S
-
i :=0, length :=inf, start :=-1
-
ในขณะที่ฉัน
-
ถ้า S[i] เหมือนกับ T[tidx] แล้ว −
-
(เพิ่ม tidx ขึ้น 1)
-
ถ้า tidx เหมือนกับ tlen แล้ว −
-
จบ :=ผม + 1
-
(ลด tidx ลง 1)
-
ในขณะที่ tidx>=0, ทำ −
-
ถ้า S[i] เหมือนกับ T[tidx] แล้ว −
-
(ลด tidx ลง 1)
-
-
(ลดลง 1)
-
-
(เพิ่ม i ขึ้น 1)
-
(เพิ่ม tidx ขึ้น 1)
-
ถ้าสิ้นสุด - i <ความยาว แล้ว −
-
length :=end - i
-
เริ่ม :=ฉัน
-
-
-
-
(เพิ่ม i ขึ้น 1)
-
-
หากการเริ่มต้นไม่เท่ากับ -1 แล้ว −
-
สำหรับการเริ่มต้น i :=start เมื่อฉัน
-
ret :=ret + S[i]
-
-
-
รีเทิร์น
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#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"
