LeetCode 刷题第一阶段Longest Common Prefix & Implement Trie

前缀, 词频问题一般有两种解法，一种暴力枚举一种 trie 。出于学习考虑 此次用 trie 解决。而且就我所知的面试题中今年trie出现频率非常高。PS。虽然我神奇地听说过考察用DP解决这个问题的三哥面试官。。。如果有观众知道怎么用DP解， 还望赐教。

The next figure shows a trie with the words “tree”, “trie”, “algo”, “assoc”, “all”, and “also.”

Note that every vertex of the tree does not store entire prefixes or entire words. The idea is that the program should remember the word that represents each vertex while lower in the tree. ( from topcoder)

典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是最大限度地减少无谓的字符串比较，查询效率比较高。

Trie的核心思想是空间换时间，利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

它有3个基本性质：

1. 根节点不包含字符，除根节点外每一个节点都只包含一个字符。
2. 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
3. 每个节点的所有子节点包含的字符都不相同。

使用范围

     既然学Trie树，我们肯定要知道这玩意是用来干嘛的。

     第一：词频统计。

            可能有人要说了，词频统计简单啊，一个hash或者一个堆就可以打完收工，但问题来了，如果内存有限呢？还能这么

             玩吗？所以这里我们就可以用trie树来压缩下空间，因为公共前缀都是用一个节点保存的。

     第二: 前缀匹配

            就拿上面的图来说吧，如果我想获取所有以"a"开头的字符串，从图中可以很明显的看到是：and,as,at，如果不用trie树，

            你该怎么做呢？很显然朴素的做法时间复杂度为O(N²) ，那么用Trie树就不一样了，它可以做到h，h为你检索单词的长度。

===========================================================

Leetcode：

Implement Trie (Prefix Tree)

Implement a trie with insert, search, and startsWith methods.

=========================================================

思路不难，但是边界问题太多。。。本人之前写出了一个Bug硬是没有找出来。。。后来大神帮忙看才找出来。。我把isWord标在了正确值的上面一个好像，同时查找的时候也查的是上一个。所以出现了95%的test 能过。。不过代码还可以优化。。。待我回头再来。。。
=========================================================
Code:





欢迎指正