实现字典树 (前缀树)

题目描述

实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。

说明:
你可以假设所有的输入都是由小写字母 a-z 构成的。保证所有输入均为非空字符串。

示例

Trie trie = new Trie();

trie.insert("apple");
trie.search("apple");   // 返回 true
trie.search("app");     // 返回 false
trie.startsWith("app"); // 返回 true
trie.insert("app");   
trie.search("app");     // 返回 true

解答

public class Trie {

    private TrieNode root;

    /** Initialize your data structure here. */
    public Trie() {

        root = new TrieNode( ' ');

    }

    /** Inserts a word into the trie. */
    public void insert(String word) {

        TrieNode tn = root;

        char[] chars = word.toCharArray();

        for(char c : chars){
            if(tn.children[c - 'a'] == null){
                tn.children[c - 'a'] = new TrieNode(c);
            }
            tn = tn.children[c - 'a'];
        }
        tn.isWord = true;
    }

    /** Returns if the word is in the trie. */
    public boolean search(String word) {

        TrieNode tn = root;

        char[] chars = word.toCharArray();

        for(char c : chars){
            if(tn.children[c - 'a'] == null){
                return false;
            }else{
                tn = tn.children[c - 'a'];
            }
        }

        return tn.isWord;
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {

        TrieNode tn = root;

        char[] chars = prefix.toCharArray();

        for(char c : chars){
            if(tn.children[c - 'a'] == null){
                return false;
            }else{
                tn = tn.children[c - 'a'];
            }
        }

        return true;
    }
}

class TrieNode {

    public char val;
    public boolean isWord;
    public TrieNode[] children = new TrieNode[26];

    public TrieNode(){};

    TrieNode(char c){
        TrieNode node = new TrieNode();
        node.val = c;
    }
}

由于默认只输入小写字母，因此直接将每个节点的子节点定位为26个，按a-z顺序依次存储，省去了子节点字母遍历的麻烦。