字典树与实际应用：拼写检查与搜索建议

1、每个节点代表一个字符。
2、从根节点到任何一个节点，路径上经过的字符连接起来就是该节点所代表的字符串。
3、每个节点可以包含多个子节点，每个子节点代表不同的字符。

public class Trie {

    private final int CHAR_ENUM_SIZE = 26;

    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    public static void main(String[] args) {
        String[] stringArr = {"dasdbehfb", "fsdfds", "asda", "dasdasdrew", "rewrewrrw"};
        Trie trie = new Trie();
        for (String s : stringArr) {
            trie.insert(s);
        }
        if (trie.isExist(stringArr[1])) {
            System.out.println(stringArr[1] + "存在");
        }
        if (!trie.isExist("abc")) {
            System.out.println("abc不存在");
        }
        // output
        // fsdfds存在
        // abc不存在
    }

    /**
     * 插入字符串
     *
     * @param str
     * @return
     */
    public void insert(String str) {
        TrieNode currentTrieNode = root;
        for (char c : str.toCharArray()) {
            if (currentTrieNode.nextNode[c - 'a'] == null) {
                currentTrieNode.nextNode[c - 'a'] = new TrieNode();
            }
            currentTrieNode = currentTrieNode.nextNode[c - 'a'];
            currentTrieNode.count = +1;
        }
    }

    /**
     * 查询字符是否存在
     *
     * @param str
     * @return
     */
    public Boolean isExist(String str) {
        TrieNode currentTrieNode = root;
        for (char c : str.toCharArray()) {
            if (currentTrieNode.nextNode[c - 'a'] == null) {
                return false;
            }
            currentTrieNode = currentTrieNode.nextNode[c - 'a'];
        }
        return true;
    }

    /***
     * 字典树节点
     */
    class TrieNode {
        /**
         * 统计存在该前缀的字符个数
         */
        int count;
        TrieNode[] nextNode = new TrieNode[CHAR_ENUM_SIZE];

        public TrieNode() {
            count = 0;
        }
    }
}