Khớp mẫu CamelCase trong C++

Mô tả bài toán

Cho danh sách truy vấn queries và một mẫu pattern. Truy vấn khớp mẫu nếu có thể chèn các chữ thường vào mẫu để được truy vấn (chữ hoa phải khớp chính xác và đúng thứ tự).

Ví dụ: queries=["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"], pattern="FB" → [true,false,true,false,false].

Giải thuật Trie (Cây tiền tố)

1. Xây dựng Trie từ pattern (chỉ các ký tự trong pattern).
2. Với mỗi truy vấn, duyệt Trie:
   • Nếu ký tự khớp con trỏ Trie → đi xuống.
   • Nếu không khớp nhưng là chữ thường → bỏ qua (cho phép chèn).
   • Nếu không khớp và là chữ HOA → thất bại.
3. Cuối truy vấn: khớp nếu đã đến nút kết thúc của pattern (isEnd) và không thất bại.

Cài đặt C++

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

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

class Solution {
    void insert(Node* root, string& s) {
        for (char c : s) {
            if (!root->child.count(c)) root->child[c] = new Node();
            root = root->child[c];
        }
        root->isEnd = true;
    }
public:
    vector<bool> camelMatch(vector<string>& queries, string pattern) {
        Node* root = new Node();
        insert(root, pattern);
        vector<bool> ans;
        for (auto& q : queries) {
            Node* cur = root;
            bool ok = true;
            for (char c : q) {
                if (cur->child.count(c)) cur = cur->child[c];
                else if (c >= 'A' && c <= 'Z') { ok = false; break; }
            }
            ans.push_back(cur->isEnd && ok);
        }
        return ans;
    }
};

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

Độ phức tạp

• Thời gian: O(sum |queries[i]|).
• Không gian: O(|pattern|) cho Trie.