การจับคู่แบบ CamelCase ใน C++

ให้รายการคำถาม (queries) และ pattern ต้องการคืนอาร์เรย์ boolean ที่ answer[i] = true ก็ต่อเมื่อ queries[i] จับคู่ (match) กับ pattern โดยนิยามว่า: สามารถแทรกตัวอักษรเล็ก (lowercase) เข้าไปใน pattern ได้จนเท่ากับ query

ตัวอย่าง: queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"], pattern = "FB" → [true,false,true,false,false]

ขั้นตอนการแก้ปัญหา (Trie)

1. สร้าง Trie จาก pattern (เฉพาะตัวอักษรใน pattern)
2. สำหรับแต่ละ query:
   • เดินตาม Trie ตามตัวอักษรของ query
   • ถ้าตัวอักษรมีใน Trie → เดินต่อ
   • ถ้าไม่มีใน Trie แตเป็นตัวพิมพ์ใหญ่ (A-Z) → ไม่จับคู่ (เพราะ pattern ไม่มีตัวนั้น)
   • ถ้าไม่มีใน Trie และเป็นตัวเล็ก → ข้ามไป (ถือว่าเป็นตัวที่แทรกเพิ่ม)
3. จับคู่สำเร็จก็ต่อเมื่อเดินจนจบ query และอยู่ที่โหนดสิ้นสุดของ pattern

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

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

struct Node {
    bool isEnd = false;
    unordered_map<char, Node*> child;
};

class Solution {
public:
    void insertNode(Node* head, string s) {
        Node* curr = head;
        for (char c : s) {
            if (!curr->child[c]) curr->child[c] = new Node();
            curr = curr->child[c];
        }
        curr->isEnd = true;
    }
    vector<bool> camelMatch(vector<string>& queries, string pattern) {
        Node* head = new Node();
        insertNode(head, pattern);
        vector<bool> ans(queries.size());
        for (int i = 0; i < queries.size(); i++) {
            Node* curr = head;
            bool ok = true;
            for (char c : queries[i]) {
                if (curr->child.count(c)) curr = curr->child[c];
                else if (c >= 'A' && c <= 'Z') { ok = false; break; }
            }
            ans[i] = curr->isEnd && ok;
        }
        return ans;
    }
};

int main() {
    vector<string> v1 = {"FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"};
    Solution ob;
    for (bool b : ob.camelMatch(v1, "FB")) cout << b << ", ";
}

Input

["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"] "FB"

Output

[1, 0, 1, 1, 0, ]