Number of Matching Subsequences ใน C++: นับคำใน Dictionary ที่เป็น Subsequence

โจทย์

กำหนดสตริง S และ dictionary words[] นับว่ามีกี่คำที่เป็น subsequence ของ S

ตัวอย่าง: S="abcde", words=["a","bb","acd","ace"] → 3 ("a","acd","ace")

แนวคิด: Bucket by Next Character + BFS Style

จัดกลุ่มคำตามตัวอักษรถัดไปที่ต้องจับคู่ อ่าน S ซ้าย→ขวา ย้ายคำไปกลุ่มถัดไปเมื่อจับคู่ได้

ขั้นตอน

1. สร้าง map<char, vector<string>> buckets
2. ใส่คำทุกคำลง buckets[word[0]]
3. ans = 0
4. ลูปตัวอักษร c ใน S:
   • ดึง bucket = buckets[c] ล้าง buckets[c]
   • ลูปคำใน bucket:
     • ถ้า word.size() == 1 → ans++
     • มิฉะนั้น → ใส่ word.substr(1) ลง buckets[word[1]]
5. คืน ans

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

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

class Solution {
public:
    int numMatchingSubseq(string S, vector<string>& words) {
        unordered_map<char, vector<string>> buckets;
        for (auto& w : words) buckets[w[0]].push_back(w);
        
        int ans = 0;
        for (char c : S) {
            auto it = buckets.find(c);
            if (it == buckets.end()) continue;
            
            vector<string> curr = move(it->second);
            buckets.erase(it);
            
            for (auto& w : curr) {
                if (w.size() == 1) ans++;
                else buckets[w[1]].push_back(w.substr(1));
            }
        }
        return ans;
    }
};

int main() {
    Solution ob;
    string s = "abcde";
    vector<string> v = {"a","bb","acd","ace"};
    cout << ob.numMatchingSubseq(s, v); // 3
    return 0;
}

อินพุต / เอาต์พุต

Input: "abcde" ["a","bb","acd","ace"]

Output: 3

ความซับซ้อน

• Time: O(|S| + Σ|words[i]|) - แต่ละตัวอักษรใน words ประมวลผล 1 ครั้ง
• Space: O(Σ|words[i]|)