字典树的一种实现

该篇文字主要是leetcode算法问题第208题的代码实现， 相关链接

1.字典树是什么

字典树（Trie）又称为单词查找树，是一种前缀树,哈希树的一种变种。字典树排序和保存着大量字符串，经常用作文本的词频统计。由于利用了公共前缀字符串，故可以减少很多无谓的字符串之间的比较，从而大大提高查询效率

2.字典树的特性

1. 字典树是一种树形数据结构，其根节点不包含字符，其余节点每个节点包含一个字符。
2. 将从根节点到某一具体节点所经过的路径上的所有字符连接起来，便是该具体节点所对应的字符串
3. 每个节点的子节点所包含的字符各不相同

3.字典树的代码实现

Code

class Trie {
    
    private TrieNode root;

    private class TrieNode {
        private char end;       //end of word
        private char val;
        TrieNode[] children = new TrieNode[26];
        TrieNode(){}

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


    /** Initialize your data structure here. */
    public Trie() {
        this.root = new TrieNode(' ');
    }

    /** Inserts a word into the trie. */
    public void insert(String word) {
        TrieNode node = root;
        for (int i=0; i<word.length(); i++) {
            char cur = word.charAt(i);
            if (null == node.children[cur - 'a']) {
                node.children[cur - 'a'] = new TrieNode(cur);
            }
            node = node.children[cur - 'a'];
        }
        node.end = '#';
    }

    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        TrieNode node = root;
        for (int i=0; i<word.length(); i++) {
            char ch = word.charAt(i);
            if (node.children[ch - 'a'] == null)
                return false;
            node = node.children[ch - 'a'];
        }
        return node.end == '#';
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        TrieNode node = root;
        for (int i=0; i<prefix.length(); i++) {
            char ch = prefix.charAt(i);
            if (null == node.children[ch - 'a'])
                return false;

            node = node.children[ch - 'a'];

        }
        return true;
    }
}