Longest Word in Dictionary through Deleting ใน C++

ให้สตริง s และดิกชันนารี d หาคำที่ยาวที่สุดใน d ที่สามารถสร้างได้โดยการลบตัวอักษรบางส่วนจาก s หากมีหลายคำ ให้คำที่มาก่อนตามลำดับเล็กซิโคกราฟิก

ตัวอย่าง: s="abpcplea", d=["ale","apple","monkey","plea"] → "apple"

วิธีแก้ปัญหา (Two Pointers Subsequence Check)

1. ฟังก์ชัน isSubsequence(s1, s2): ตรวจสอบว่า s2 เป็น subsequence ของ s1
   • ใช้ two pointers i, j วิ่งบน s1, s2
2. จาก main: วนทุกคำใน d:
   • ถ้าคำยาวกว่าคำตอบปัจจุบัน หรือ ยาวเท่ากันแต่นำหน้าด้านเล็กซิโคกราฟิก
   • และเป็น subsequence → อัปเดตคำตอบ

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

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

class Solution {
public:
    bool isSubsequence(string s1, string s2) {
        int j = 0;
        for (int i = 0; i < s1.size(); i++) {
            if (s2[j] == s1[i]) {
                j++;
                if (j == s2.size()) break;
            }
        }
        return j == s2.size();
    }
    
    string findLongestWord(string s, vector<string>& d) {
        string ans = "";
        for (int i = 0; i < d.size(); i++) {
            string x = d[i];
            if (x.size() > ans.size() || (x.size() == ans.size() && x < ans)) {
                if (isSubsequence(s, x)) ans = x;
            }
        }
        return ans;
    }
};

int main() {
    vector<string> v = {"ale","apple","monkey","plea"};
    Solution ob;
    cout << ob.findLongestWord("abpcplea", v);
    return 0;
}

Input

"abpcplea" ["ale","apple","monkey","plea"]

Output

apple