Implement a trie with insert, search, and startsWith methods.Note:You may assume that all inputs are consist of lowercase letters a-z.

参考百度百科：

a trie, also called digital tree and sometimes  or prefix tree (as they can be searched by prefixes)

The time complexity to insert and to search is O(m), where m is the length of the string.

标准Trie树的应用和优缺点

     (1) 全字匹配：确定待查字串是否与集合的一个单词完全匹配。如上代码fullMatch()。

     (2) 前缀匹配：查找集合中与以s为前缀的所有串。

 

     注意：Trie树的结构并不适合用来查找子串。这一点和前面提到的PAT Tree以及后面专门要提到的Suffix Tree的作用有很大不同。

 

      优点： 查找效率比与集合中的每一个字符串做匹配的效率要高很多。在o(m)时间内搜索一个长度为m的字符串s是否在字典里。Predictable O(k) lookup time where k is the size of the key

      缺点：标准Trie的空间利用率不高，可能存在大量结点中只有一个子结点，这样的结点绝对是一种浪费。正是这个原因，才迅速推动了下面所讲的压缩trie的开发。

什么时候用Trie?

It all depends on what problem you're trying to solve. If all you need to do is insertions and lookups, go with a hash table. If you need to solve more complex problems such as prefix-related queries, then a trie might be the better solution. 

 像word search II就是跟前缀有关，如果dfs发现当前形成的前缀都不在字典中，就没必要再搜索下去了，所以用trie不用hashSet

1 class TrieNode { 2     // Initialize your data structure here. 3     int num; //How many words go through this TrieNode 4     TrieNode[] son; //collection of sons 5     boolean isEnd; 6     char val; 7      8     public TrieNode() { 9         this.num = 0;10         this.son = new TrieNode[26];11         this.isEnd = false;12     }13 }14 15 public class Trie {16     private TrieNode root;17 18     public Trie() {19         root = new TrieNode();20     }21 22     // Inserts a word into the trie.23     public void insert(String word) {24         if (word==null || word.length()==0) return;25         char[] arr = word.toCharArray();26         TrieNode node = this.root;27         for (int i=0; i