前缀树Trie

前缀树又称字典树，通过树形结构存储单词，适用于判断单词及其前缀是否存在。具体介绍参见leetcode 208：https://leetcode-cn.com/problems/implement-trie-prefix-tree/

class Trie {
    class Node {
        Node[] list;
        boolean isEnd;
        public Node() {
            list = new Node[26];
        }

        public boolean contains(char c) {
            return list[c - 'a'] != null;
        }

        public void put(char c) {
            if (list[c - 'a'] == null)
                list[c - 'a'] = new Node();
        }

        public Node get(char c) {
            return list[c - 'a'];
        }

        public void setIsEnd() {
            this.isEnd = true;
        }

        public boolean isEnd() {
            return isEnd;
        }
    }

    private Node root;

    /** Initialize your data structure here. */
    public Trie() {
        root = new Node();
    }
    
    /** Inserts a word into the trie. */
    public void insert(String word) {
        Node node = root;
        for (int i=0; i<word.length(); i++) {
            char c = word.charAt(i);
            node.put(c);
            node = node.get(c);                
        }
        node.setIsEnd();
    }
    
    private Node searchPrefix(String word) {
        Node node = root;
        for (int i=0; i<word.length(); i++) {
            char c = word.charAt(i);
            if (!node.contains(c))
                return null;
            node = node.get(c);              
        }
        return node;
    }

    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        Node n = this.searchPrefix(word);
        return n != null && n.isEnd();
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        Node n = this.searchPrefix(prefix);
        return n != null;
    }
}