C++で実装する単語辞書データ構造：追加と検索(Trie木によるワイルドカード対応)

問題概要

本記事では、次の2つの操作をサポートするデータ構造をC++で設計・実装する方法を解説します。

• addWord(word):単語を辞書へ追加する
• search(word):単語を検索する

search(word)は、通常の単語だけでなく、小文字アルファベット(a〜z)とドット(.)のみで構成されたパターン文字列も扱えます。ドットは任意の1文字に一致するワイルドカードとして機能します。

例えば、「bad」「dad」「mad」の3つの単語を登録した状態での検索結果は以下の通りです。

• search("pad") → false
• search("bad") → true
• search(".ad") → true(先頭が任意の1文字でも一致)
• search("b..") → true(残り2文字が任意でも一致)

解決のアプローチ:Trie(トライ木)の活用

この問題は、文字列を接頭辞ごとに管理する木構造であるTrie(トライ木)を用いることで効率的に解けます。全体の手順は以下の通りです。

1. insertNode()を定義する。ルートノードへの参照と文字列sを受け取り、以下のように動作します。

   • curr := head、n := 文字列sの長さ と初期化
   • iを0からn−1まで繰り返す:
     • x := s[i]
     • currの子child[x]が存在しなければ、新規ノードを作成してchild[x]に設定
     • curr := currのchild[x]へ移動
   • 最終ノードのisEndフラグをtrueにセット(ここが単語の終端であることを示す)

2. addWord()からこのinsertNode()を呼び出します。

3. check()を定義する。現在のノードcurr、文字列s、インデックスidx(初期値0)を受け取り、再帰的に照合を行います。

   • idx == s.size()なら、currのisEndを返す(単語が完全に一致したか判定)
   • s[idx]がドットの場合:
     • iを0から25まで繰り返す:
       • x := 'a' + i
       • currのchild[x]が存在し、かつcheck(child[x], s, idx+1)がtrueならtrueを返す
   • それ以外の場合:
     • x := s[idx]
     • currのchild[x]が存在し、かつcheck(child[x], s, idx+1)がtrueならtrueを返す
   • どの分岐にも当てはまらなければfalseを返す

4. search()では curr := head とし、check(curr, word, 0) の結果を返します。

ポイントは、ドットに遭遇した際に全26通りの子ノードに対して再帰的に探索(バックトラック)を行う点です。これにより、ワイルドカードを含むパターンとの一致判定が可能になります。

C++による実装例

以下のコードで実際の動作を確認してみましょう。

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

struct Node {
    bool isEnd;
    map<char, Node*> child;
    Node() {
        isEnd = false;
    }
};

class WordDictionary {
public:
    Node* head;
    WordDictionary() {
        head = new Node();
    }
    void insertNode(Node* head, string s) {
        Node* curr = head;
        int n = s.size();
        for (int i = 0; i < n; i++) {
            char x = s[i];
            if (!curr->child[x]) {
                curr->child[x] = new Node();
            }
            curr = curr->child[x];
        }
        curr->isEnd = true;
    }
    void addWord(string word) {
        insertNode(head, word);
    }
    bool check(Node* curr, string s, int idx = 0) {
        if (idx == s.size()) return curr->isEnd;
        bool ok = false;
        if (s[idx] == '.') {
            for (int i = 0; i < 26; i++) {
                char x = 'a' + i;
                if (curr->child[x] && check(curr->child[x], s, idx + 1)) return true;
            }
        } else {
            char x = s[idx];
            if (curr->child[x] && check(curr->child[x], s, idx + 1)) return true;
        }
        return false;
    }
    bool search(string word) {
        Node* curr = head;
        return check(curr, word);
    }
};

int main() {
    WordDictionary ob;
    ob.addWord("bad");
    ob.addWord("dad");
    ob.addWord("mad");
    cout << ob.search("pad") << endl;
    cout << ob.search("bad") << endl;
    cout << ob.search(".ad") << endl;
    cout << ob.search("b..") << endl;
}

入力

WordDictionaryを初期化した後、main()関数内でaddWord()とsearch()を順に呼び出します。

出力

0
1
1
1

動作の解説と計算量

• search("pad") → 0(false):「pad」は登録されていないため一致しません。
• search("bad") → 1(true):登録済みの単語そのものなので一致します。
• search(".ad") → 1(true):先頭のドットが「b」「d」「m」のいずれかにマッチし、「ad」以降も一致します。
• search("b..") → 1(true):「b」の後に続く2文字がワイルドカードにより「ad」にマッチします。

計算量を見てみましょう。addWordは単語長をLとするとO(L)で処理できます。一方searchは、ワイルドカードを含まない場合はO(L)ですが、ドットが含まれる場合は各ドット位置で最大26方向に探索が分岐するため、最悪でO(26^d × L)(dはドットの個数)となります。ただし、実際にはTrie上に存在しない枝は早期に打ち切られるため、多くの場合これより大幅に高速に動作します。

このように、Trie木と再帰的な深さ優先探索(DFS)を組み合わせることで、前方一致の高速な検索に加え、柔軟なパターンマッチングにも対応できる単語辞書を実現できます。