示例 1：
输入: ["flower","flow","flight"]
输出: "fl"
复制代码示例 2：
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
复制代码说明：
所有输入仅包含大写字母 a-z。
解决方案一：一一比较
解题思路：从前面的字符串比较中获取公共前缀
画图帮助理解：
代码实现：
var longestCommonPrefix = function(strs) {
if (strs === null || strs.length === 0) return "";
let prevs = strs[0]
for(let i = 1; i < strs.length; i++) {
let j = 0
for(; j < prevs.length && j < strs[i].length; j++) {
if(prevs.charAt(j) !== strs[i].charAt(j)) break
}
prevs = prevs.substring(0, j)
if(prevs === "") return ""
}
return prevs
};
复制代码时间复杂度：O(s)，s是所有字符串的字符数之和
空间复杂度：O(1)
方案2：只需要最大和最小字符串的最长公共前缀
解决思路：获取链表中的最大最小字符串。最小字符串和最大字符串的最长公共前缀也是其他字符串的公共前缀，也就是字符串字段的最长公共前缀。
比如abc,abcd,ab,ac,最小ab和最大ac的最长公共前缀也必须是abc,abcd的公共前缀
画图帮助理解：
代码实现：
var longestCommonPrefix = function(strs) {
if (strs === null || strs.length === 0) return "";
if(strs.length === 1) return strs[0]
let min = 0, max = 0
for(let i = 1; i strs[i]) min = i
if(strs[max] < strs[i]) max = i
}
for(let j = 0; j < strs[min].length; j++) {
if(strs[min].charAt(j) !== strs[max].charAt(j)) {
return strs[min].substring(0, j)
}
}
return strs[min]
};
复制代码时间复杂度：O(n+m)向有限的空间输入超长的字符串是哪一种攻击手段，n为链表的宽度，m为字符串链表中最短字符的宽度
空间复杂度：O(1)
解决方案 3：分而治之的战略和融合理念
分而治之，顾名思义就是分而治之，把一个复杂的问题分成两个或多个相似的子问题，把子问题再分成更小的子问题，直到更小的子问题可以被简单地解决和解决。子问题，原问题的解是子问题的解的组合。
这个问题是一个典型的分而治之的策略问题：
画图帮助理解：
以abc、abcd、ab、ac为例：
代码实现：
var longestCommonPrefix = function(strs) {
if (strs === null || strs.length === 0) return "";
return lCPrefixRec(strs)
};
// 若分裂后的两个数组长度不为 1，则继续分裂
// 直到分裂后的数组长度都为 1，
// 然后比较获取最长公共前缀
function lCPrefixRec(arr) {
let length = arr.length
if(length === 1) {
return arr[0]
}
let mid = Math.floor(length / 2),
left = arr.slice(0, mid),
right = arr.slice(mid, length)
return lCPrefixTwo(lCPrefixRec(left), lCPrefixRec(right))
}
// 求 str1 与 str2 的最长公共前缀
function lCPrefixTwo(str1, str2) {
let j = 0
for(; j < str1.length && j < str2.length; j++) {
if(str1.charAt(j) !== str2.charAt(j)) {
break
}
}
return str1.substring(0, j)
}
复制代码时间复杂度：O(s)，s是所有字符串的字符数之和
空间复杂度：O(m*logn)，n为链表的宽度向有限的空间输入超长的字符串是哪一种攻击手段，m为字符串链表中最长字符的宽度
解决方案 4：Trie 树（字典树）
Trie树，也称为字典树或前缀树，顾名思义，它是一种用于处理字符串匹配问题的数据结构，也是一种用于在集合中查找固定前缀字符串的数据结构。
解决思路：构建Trie树，字符串字段的最长公共序列是从根节点开始遍历树，直到：
到目前为止，传递的字符是字符串字段的最长公共前缀
画图帮助理解：
构建Trie树，以abc、abcd、ab、ac为例：
代码实现：
var longestCommonPrefix = function(strs) {
if (strs === null || strs.length === 0) return "";
// 初始化 Trie 树
let trie = new Trie()
// 构建 Trie 树
for(let i = 0; i < strs.length; i++) {
if(!trie.insert(strs[i])) return ""
}
// 返回最长公共前缀
return trie.searchLongestPrefix()
};
// Trie 树
var Trie = function() {
this.root = new TrieNode()
};
var TrieNode = function() {
// next 放入当前节点的子节点
this.next = {};
// 当前是否是结束节点
this.isEnd = false;
};
Trie.prototype.insert = function(word) {
if (!word) return false
let node = this.root
for (let i = 0; i < word.length; i++) {
if (!node.next[word[i]]) {
node.next[word[i]] = new TrieNode()
}
node = node.next[word[i]]
}
node.isEnd = true
return true
};
Trie.prototype.searchLongestPrefix = function() {
let node = this.root
let prevs = ''
while(node.next) {
let keys = Object.keys(node.next)
if(keys.length !== 1) break
if(node.next[keys[0]].isEnd) {
prevs += keys[0]
break
}
prevs += keys[0]
node = node.next[keys[0]]
}
return prevs
}
复制代码时间复杂度：O(s+m)，s是所有字符串的字符数之和，m是字符串列表中最长字符的宽度，构建Trie树需要O(s) ，最长公共前缀查询操作的复杂度是O(m)
空间复杂度：构建 Trie 树的 O(s)
