トライ木データ構造パターン

中級

カテゴリ: trees

概要

トライ木（Trie、プレフィックスツリーとも呼ばれる）は、文字列の集合を効率的に格納・検索するための木構造です。各ノードは文字を表し、ルートから特定のノードへのパスが文字列を形成します。トライ木は、文字列の前方一致検索、自動補完、スペルチェック、最長共通接頭辞の検索など、文字列関連の問題に特に有効です。検索操作はO(m)の時間複雑度で行えます（mは検索する文字列の長さ）。

コードテンプレート

Java

Python

- トライ木の実装
class TrieNode {
    private TrieNode[] children;
    private boolean isEndOfWord;
    
    public TrieNode() {
        children = new TrieNode[26]; // 英小文字のみを想定
        isEndOfWord = false;
    }
    
    public TrieNode[] getChildren() {
        return children;
    }
    
    public boolean isEndOfWord() {
        return isEndOfWord;
    }
    
    public void setEndOfWord(boolean isEndOfWord) {
        this.isEndOfWord = isEndOfWord;
    }
}

class Trie {
    private TrieNode root;
    
    public Trie() {
        root = new TrieNode();
    }
    
    // 単語の挿入
    public void insert(String word) {
        TrieNode current = root;
        
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (current.getChildren()[index] == null) {
                current.getChildren()[index] = new TrieNode();
            }
            current = current.getChildren()[index];
        }
        
        current.setEndOfWord(true);
    }
    
    // 単語の検索
    public boolean search(String word) {
        TrieNode node = searchPrefix(word);
        return node != null && node.isEndOfWord();
    }
    
    // 接頭辞の検索
    public boolean startsWith(String prefix) {
        return searchPrefix(prefix) != null;
    }
    
    // 共通メソッド: 指定された文字列のノードを検索
    private TrieNode searchPrefix(String word) {
        TrieNode current = root;
        
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (current.getChildren()[index] == null) {
                return null;
            }
            current = current.getChildren()[index];
        }
        
        return current;
    }
}

Java

ひらめきのサポート

問題文に以下のようなキーワードや特徴がある場合、このパターンの適用を検討してみましょう。

トライ木プレフィックスツリーTrie前方一致検索自動補完文字列検索接頭辞単語辞書スペルチェック文字列集合木構造

チャート式ひらめきポイント

問題を読んだときに、「ソート済み配列で何かを見つける」「二つの要素の関係を調べる」「効率的に配列を操作する」などの特徴があれば、双指針パターンが適用できる可能性が高いです。特に、O(n²)の計算量を避けたい場合に有効です。

このパターンを使用する問題例

1
単語の検索（Implement Trie）: トライ木を実装して単語の挿入、検索、前方一致検索を行う
2
単語検索II（Word Search II）: 文字盤上で見つけられる単語をトライ木を使って効率的に検索する
3
単語の置換（Replace Words）: 文章内の単語を最短の接頭辞に置き換える
4
自動補完システム（Design Search Autocomplete System）: 検索履歴に基づいて自動補完候補を提供する
5
最長共通接頭辞（Longest Common Prefix）: 文字列集合の最長共通接頭辞を見つける

トライ木データ構造パターン

概要

コードテンプレート

ひらめきのサポート

チャート式ひらめきポイント

このパターンを使用する問題例

関連するパターン