leetcode14--最长公共前缀 前缀树_最长公共前缀 trie

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

示例 1:

输入: ["flower","flow","flight"]
输出: "fl"

示例 2:

输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。

说明:

所有输入只包含小写字母 a-z 。

本题大概有四种解法：

1. 横向扫描：比较前两个字符串的公共前缀，将结果与第三个字符串进行比较得到前三个字符串的公共前缀，再将结果与第四个字符串比较，直至最后一个字符串，时间复杂度为O(n*m), n是字符串的个数，m是字符串的平均长度。

2. 纵向扫描：扫描每个字符串的第一个字符，如果全部相等则继续扫描每个字符串的第二个字符，当不是全部相等时返回前面扫描过的子串，时间复杂度为O(n*m)

3. 前缀树：所求最长公共前缀一定是每个字符串的前缀子串，故可以把其中一个字符串作为标准，然后将其前缀串与所有其他字符串进行比较，判断该前缀串是否是所有其他字符串的前缀

4.前缀树：以其中一个字符串为标准，遍历该字符串在树中的节点信息，第一个出现分支的节点即为要找的分割点，从根节点到该点的字符串即为所求最长公共前缀

一 前缀树
 概述
前缀树又名字典树，单词查找树，Trie树，是一种多路树形结构，是哈希树的变种，和hash效率有一拼，是一种用于快速检索的多叉树结构。
典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。
Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。 
Trie树也有它的缺点，