14. 最长公共前缀
14. 最长公共前缀
力扣题目链接[1]
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
「示例 1：」
输入：strs = ["flower","flow","flight"]
输出："fl"
「提示：」
1 <= strs.length <= 2000 <= strs[i].length <= 200strs[i]仅由小写英文字母组成
思路：
首先考虑逐个字符串对比，来确定最终的公共前缀。按照题目提示，数组至少会有一项，因此不需要做空置判断。
假设第一个数组元素就是最长的前缀。然后从数组的第二个元素开始遍历。然后依次对比数组的当前元素和最长前缀的每个字符，直到不一样为止。那么前面一样的字符串就是最新的最长前缀。如果对比时发现前缀已经是空字符串，便提前返回，无需再判断。
逐个比较
/**
* @param {string[]} strs
* @return {string}
*/
var longestCommonPrefix = function(strs) {
let prevs = strs[0];
for (let i = 1; i < strs.length; i++) {
let j = 0;
while(j < prevs.length && j < strs[i].length) {
if (prevs[j] !== strs[i][j]) break;
j++;
}
prevs = prevs.slice(0, j);
if (!prevs) return '';
}
return prevs;
};
优化
上述方法是将每个字符串进行比较，来获取最长前缀。其实起决定性因素的是最大字符串和最小字符串。只需要对比两者的公共前缀，也就是整个数组的公共前缀。那么做法就是先进行一次遍历，找出最大字符串和最小字符串的索引。然后依次对比两者的每个字符，即可找出最长前缀。
本题的另外一种解法也可以采用字典树进行求解。
字典树
此方法是效率最高的一种方法。通过构建字典树，可以字典树的基础上去查找最长公共前缀。大概逻辑是：
字符串数组的最长公共序列就为从根节点开始遍历树，直到：
- 遍历节点存在超过一个子节点的节点
- 或遍历节点为一个字符串的结束字符
为止，走过的字符为字符串数组的最长公共前缀。
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
}
总结
本题考查字典树的构建与公共前缀的查找。前端领域，一般不太能遇到使用字典树这种思想的场景，但是这种思路也是要掌握的。尤其适合有大量相同前缀的数据，使用字典树的效率会非常高。
参考资料
[1]
力扣题目链接: https://leetcode-cn.com/problems/longest-common-prefix/
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2022-04-13，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
