Minimum Window Subsequence (หน้าต่างย่อยขั้นต่ำ) ใน C++

สมมติว่าเรามีสตริงสองสตริง S และ T เราต้องหา substring W ที่สั้นที่สุดของ S ทำให้ T เป็น subsequence ของ W หากไม่มีหน้าต่างใน S ที่ครอบคลุมตัวอักษรทั้งหมดใน T ให้คืนค่าสตริงว่าง หากมีหลายหน้าต่าง ให้คืนค่าตัวที่มีดัชนีเริ่มต้นซ้ายสุด

ดังนั้น หากอินพุทคือ S = "abcdebdde", T = "bde" ผลลัพธ์จะเป็น "bcde" เนื่องจากมันเกิดขึ้นก่อน "bdde" "deb" ไม่ใช่หน้าต่างที่เล็กกว่า เพราะองค์ประกอบของ T ในหน้าต่างต้องเกิดขึ้นตามลำดับ

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้:

• tidx := 0, tlen := ขนาดของ T

• n := ขนาดของ S

• i := 0, length := INF, start := -1

• while i < n:

  • ถ้า S[i] == T[tidx]: tidx++

  • ถ้า tidx == tlen:

    • end := i + 1

    • tidx--

    • while tidx >= 0:

      • ถ้า S[i] == T[tidx]: tidx--

      • i--

    • i++; tidx++

    • ถ้า end - i < length: length := end - i; start := i

• i++

• ถ้า start != -1: สร้าง ret จาก S[start ถึง start+length-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;
    }
};

int main() {
    Solution ob;
    cout << (ob.minWindow("abcdebdde", "bde"));
    return 0;
}

อินพุต

"abcdebdde", "bde"

เอาต์พุต

"bcde"