โปรแกรมตรวจสอบว่า string เป็น subsequence ของอีก string ใน C++

ภาพรวมปัญหา

ให้สตริง S และ T ต้องการตรวจสอบว่า S เป็น subsequence ของ T หรือไม่ (ตัวอักษรของ S ปรากฏใน T ตามลำดับ แต่ไม่จำเป็นต้องติดกัน)

ตัวอย่าง

Input: S = "abc", T = "adbrcyxd"

Output: true (1)

คำอธิบาย: a (index 0), b (index 2), c (index 5) ใน T

แนวทางแก้ปัญหา (Two Pointers)

1. Pointer i สำหรับ S, pointer j สำหรับ T
2. วนลูปจน i จบ หรือ j จบ
3. ถ้า S[i] == T[j] → i++, j++
4. มิฉะนั้น → j++ (ข้ามตัวอักษรใน T)
5. ถ้า i == S.length() → เป็น subsequence

โค้ดตัวอย่าง

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool solve(string s, string t) {
        if (s == t) return true;
        int n = s.size(), m = t.size();
        int j = 0;
        for (int i = 0; i < n && j < m; i++) {
            while (j < m && t[j] != s[i]) j++;
            if (j == m) return false;
            j++;
        }
        return true;
    }
};

int main() {
    Solution ob;
    string S = "abc", T = "adbrcyxd";
    cout << ob.solve(S, T);
    return 0;
}

ผลลัพธ์

1

โค้ดที่กระชับกว่า

bool isSubsequence(string s, string t) {
    int i = 0;
    for (char c : t) {
        if (i < s.size() && s[i] == c) i++;
    }
    return i == s.size();
}

เวอร์ชันสำหรับ Multiple Queries (Follow-up)

ถ้ามีหลาย S ต้องการตรวจสอบกับ T เดียวกัน ให้ Preprocess T:

1. สร้าง vector pos[26] เก็บตำแหน่งของแต่ละตัวอักษรใน T
2. สำหรับแต่ละ S ใช้ binary_search หาตำแหน่งถัดไปใน pos[c]

class SubsequenceChecker {
    vector pos[26];
public:
    SubsequenceChecker(string t) {
        for (int i = 0; i < t.size(); i++)
            pos[t[i] - 'a'].push_back(i);
    }
    bool isSubsequence(string s) {
        int prev = -1;
        for (char c : s) {
            auto& v = pos[c - 'a'];
            auto it = upper_bound(v.begin(), v.end(), prev);
            if (it == v.end()) return false;
            prev = *it;
        }
        return true;
    }
};

ความซับซ้อน