C++で解くキャメルケースマッチング問題：トライ木を使った実装方法

クエリ文字列のリストとパターンが与えられ、ブーリアン値のリストを返す問題を考えてみましょう。answer[i] は、queries[i] がパターンに一致する場合にのみ true となります。ここで「クエリの単語がパターンに一致する」とは、パターンの単語に小文字を挿入することでクエリと等しくできることを意味します。大文字の順序と種類は完全に一致している必要があります。

例えば、入力が ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"]、pattern = "FB" の場合、出力は [true, false, true, true, false] となります。"FooBarTest" には余分な大文字 "T" が含まれ、"ForceFeedBack" には余分な大文字 "F" が含まれるため、これらはパターン "FB" に一致しません。

解法のアプローチ

この問題は、トライ（Trie）木を用いて効率的に解くことができます。パターンをあらかじめトライ木に登録しておき、各クエリ文字列を先頭から走査して一致判定を行います。具体的な手順は以下の通りです。

• head と文字列 s を引数にとる insertNode() メソッドを定義します
• curr := head と初期化します
• i を 0 から s のサイズ - 1 までループします
  • x := s[i] とします
  • curr の child[x] が存在しない場合は、新しいノードを作成して child[x] に設定します
  • curr := curr の child[x] として次へ進みます
• 最後に curr の isEnd を true に設定します
• メイン処理では以下を実行します
• head := 新しいノードを作成し、パターンを head に挿入します。n := クエリ配列のサイズとします
• 各クエリ i に対して以下を繰り返します
  • temp := queries[i]、curr := head、m := temp のサイズ、ok := true と初期化します
  • j を 0 から m - 1 までループします
    • x := temp[j] とします
    • curr の child[x] が存在すれば、curr := curr の child[x] とします
    • 存在せず、かつ temp[j] が 'A'〜'Z' の範囲（大文字）であれば、ok := false としてループを抜けます
  • ans[i] := curr の isEnd かつ ok とします
• 最後に ans を返します

このアルゴリズムのポイントは、小文字は自由にスキップできる一方で、大文字はトライ木上に対応するノードが必ず存在しなければならないという点です。大文字の出現時に子ノードが見つからなければ、そのクエリはパターンに一致しないと即座に判断できます。また、クエリをすべて消費した時点でパターンの終端ノード（isEnd）に到達していなければ、パターン側に未消費の大文字が残っていることになるため、やはり一致とはみなしません。

例（C++）

以下の実装を見ると、より理解が深まるでしょう。

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
        cout << v[i] << ", ";
    }
    cout << "]"<<endl;
}
struct Node{
    bool isEnd;
    map <char, Node*> child;
    Node(){
        isEnd = false;
    }
};
class Solution {
    public:
    void insertNode(Node* head, string s){
        Node* curr = head;
        for(int i = 0; i < s.size(); i++){
            char x = s[i];
            if(!curr->child[x]){
                curr->child[x] = new Node();
            }
            curr = curr->child[x];
        }
        curr->isEnd = true;
    }
    vector<bool> camelMatch(vector<string>& queries, string pattern){
        Node* head = new Node();
        insertNode(head, pattern);
        int n = queries.size();
        vector <bool> ans(n);
        Node* curr;
        bool ok;
        for(int i = 0; i < n; i++){
            string temp = queries[i];
            curr = head;
            int m = temp.size();
            ok = true;
            for(int j = 0; j < m; j++){
                char x = temp[j];
                if(curr->child[x]){
                    curr = curr->child[x];
                }
                else if(temp[j] >= 'A' && temp[j] <= 'Z'){
                    ok = false;
                    break;
                }
            }
            ans[i] = curr->isEnd && ok;
        }
        return ans;
    }
};
main(){
    vector<string> v1 = {"FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"};
    Solution ob;
    print_vector(ob.camelMatch(v1, "FB"));
}

入力

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

出力

[1, 0, 1, 1, 0]

出力の 1 は true、0 は false を表します。つまり、"FooBar"、"FootBall"、"FrameBuffer" の3つだけがパターン "FB" に一致したことになります。計算量は、パターンの挿入に O(P)、すべてのクエリの判定に合計 O(Q)（P はパターン長、Q は全クエリの総文字数）となり、非常に効率的です。