208. Implement Trie (Prefix Tree

实现前缀树。

这题画个图就容易懂。
但是在写````search 和startWith```的时候我发现自己还是不够6。应该先判断false的情形，最后利用isWord判断是否到达一个word。
也就是这么写：

    public boolean search(String word) {
        TrieNode ws = root; 
        for(int i = 0; i < word.length(); i++){
            char c = word.charAt(i);
            if(ws.children[c - 'a'] == null) return false;
            ws = ws.children[c - 'a'];
        }
        return ws.isWord;
    }

完整代码：

    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;
        }
    }

    public class Trie {
        private TrieNode root;

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

        /**
         * Inserts a word into the trie.
         */
        public void insert(String word) {
            TrieNode node = root;
            for (int i = 0; i < word.length(); i++) {
                if (node.children[word.charAt(i) - 'a'] == null) {
                    node.children[word.charAt(i) - 'a'] = new TrieNode(word.charAt(i));
                }
                node = node.children[word.charAt(i) - 'a'];
            }
            node.isWord = true;
        }
        /**
         * Returns if the word is in the trie.
         */
        public boolean search(String word) {
            TrieNode node = root;
            for (int i = 0; i < word.length(); i++) {
                if (node.children[word.charAt(i) - 'a'] != null) {
                    //改变指向的方法 相当于二叉树的node.left ,right，只不过trie可以有26棵subtree
                    node = node.children[word.charAt(i) - 'a'];
                } else {
                    return false;
                }
            }
            return node.isWord;
        }

        /**
         * 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++) {
                if (node.children[prefix.charAt(i) - 'a'] == null) {
                    return false;
                }
                //改变指向的方法 相当于二叉树的node.left ,right，只不过trie可以有26棵subtree
                node = node.children[prefix.charAt(i) - 'a'];
            }
            return true;
        }
    }

又在公司熬到第二天。。。。怎么改变啊。
https://mp.weixin.qq.com/s?__biz=MzI1OTAwNDc1OA==&mid=2652834204&idx=1&sn=7010e7dd7339d7904a7f5199f69ef9c6&chksm=f19429a5c6e3a0b388712161b65e2081d7f17ddd4be9bfea10370e7e09f282c4d4639567cacd&scene=0&key=a888b8588a8bef82a8564d8aaa60b347b875069fa36c4c49b5210e41e8930d65e68ffa2a9c6e080acee61f728d57374ea6a346cc265e2c2e5f05deefa73827d6e8af75ba3686bd9e488c798881788840&ascene=0&uin=MjM2MjUzNjkwMg%3D%3D&devicetype=iMac+MacBookPro11%2C1+OSX+OSX+10.12.3+build(16D32)&version=12020110&nettype=WIFI&fontScale=100&pass_ticket=Afw5yWPXckJruFwaf1kPuXSgmOjL4412fTQGttModvX4o8Qvfd9NlK2p6hDmJXwL

http://blog.csdn.net/beiyetengqing/article/details/7856113