JavaScriptで単語の追加・ワイルドカード検索に対応したカスタムデータ構造を実装する方法

問題

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

• addWord — データ構造に単語を追加する操作です。保存には配列など、既存のデータ構造を利用できます。
• search — 登録済みの単語から、完全一致する単語、または小文字「a-z」と「.」で構成された正規表現風のパターンを検索する操作です。「.」は任意の一文字に一致します。

たとえば、次のように動作します。

addWord("sir")
addWord("car")
addWord("mad")
search("hell") === false
search(".ad") === true
search("s..") === true

実装例

以下が実際のコードです。

class MyData{
    constructor(){
        this.arr = [];
    }
}
MyData.prototype.addWord = function (word) {
    this.arr.push(word);
};
MyData.prototype.search = function (word) {
    let reg = new RegExp('^' + word + '$');
    return !!this.arr.find(el => reg.test(el));
};
const data = new MyData();
data.addWord('sir');
data.addWord('car');
data.addWord('mad');
console.log(data.search('hell')); // false
console.log(data.search('.ad'));  // true
console.log(data.search('s..'));  // true

出力

コンソールには次のように表示されます。

false
true
true

コードのポイント

• constructor() — インスタンス生成時に空の配列 this.arr を用意し、登録された単語をここに保持します。
• addWord(word) — 受け取った単語を push メソッドで配列の末尾に追加します。
• search(word) — 検索パターンの前後を ^(先頭)と $(末尾)で囲んだ RegExp オブジェクトを生成することで、部分一致ではなく完全一致として判定できます。続いて Array.prototype.find で一致する要素の有無を確認し、二重否定演算子 !! によって結果を真偽値に変換して返します。

正規表現において「.」は改行以外の任意の一文字にマッチするため、search('.ad') は「mad」だけでなく、パターンに合致するすべての登録済み単語に対して true を返します。

この「配列 + 正規表現」というアプローチはシンプルで理解しやすい一方、登録単語数が膨大になると線形探索となるため性能が劣化します。実務ではトライ木(Trie)やハッシュマップを併用することで、より高速な検索を実現できます。