题目
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例 1:
输入: ["flower","flow","flight"] 输出: "fl"
示例 2:
输入: ["dog","racecar","car"] 输出: "" 解释: 输入不存在公共前缀。
说明:
所有输入只包含小写字母 a-z。
解答
竖直扫描
一个个元素拿出来，一起比较他们的某个指针对应的字符。
累加双循环
外层设置一个index指针，一个个数组元素来比较index上的字符。
如果每个数组元素的index字符都一样，那么就加入到result当中；
或者index指向超出了数组元素的范围，也跳出循环return结果
/**
* @param {string[]} strs
* @return {string}
*/
var longestCommonPrefix = function(strs) {
let result = "";
let index = 0;
if (strs.length === 0) { // 如果输入是[]，那么就无法读取到[0]，就会报错
return result; // 加个拦截避免那种情况
}
let str = strs[0][0];
while (typeof str !== "undefined") { // 判断undefined要用typeof
console.log("=test=>", "str", str);
for (let i = 1; i < strs.length; i++) {
if (str !== strs[i][index]) {
return result;
}
}
result += str;
index++;
str = strs[0][index];
}
return result;
};
Runtime: 60 ms, faster than 74.35% of JavaScript online submissions forLongest Common Prefix.
Memory Usage: 34.9 MB, less than 68.15% of JavaScript online submissions for Longest Common Prefix.
判断undefined不能直接用相等来判断，而要用typeof
// 错误代码
while (str === undefined) {}
// 正确代码
while (typeof str !== "undefined") {}
累减双循环
作者：guanpengchn
思路是，先随便初始化一个str，然后一个个值来比对。遇到不一样就跳出来，只保留一样的部分
var longestCommonPrefix = function(strs) {
if (strs.length == 0) {
return "";
}
let ans = strs[0];
for (let i = 1; i < strs.length; i++) { // i是第几个元素
let j = 0;
for (; j < ans.length && j < strs[i].length; j++) { // j是第几位str
if (ans[j] != strs[i][j]) { // 遇到不一样就跳出
break;
}
}
ans = ans.substring(0, j); // substr最好不要用，我就换成了substring
if (!ans) { // 这个判断有机会能少走一轮循环
return ans;
}
}
return ans;
};
Runtime: 60 ms, faster than 74.35% of JavaScript online submissions forLongest Common Prefix.
Memory Usage: 34.8 MB, less than 73.04% of JavaScript online submissions for Longest Common Prefix.
累加和累减差不多
水平扫描
数组元素从前往后两两拿出来比较，相同的地方留下。比较的结果进入下一轮的两两比较。
也就是说，如果有个函数$LCP(S_1,S_2) $，输入两个字符串，输出他们共同的前缀。那么不断递归这个函数就行了。$LCP(LCP(S_1, S_2), S_3)$一直递归就完事了。
/**
* @param {string[]} strs
* @return {string}
*/
const compareTwo_minus = function(str1, str2) {
let i = 0;
for (; i < str1.length && i < str2.length; i++) {
if (str1[i] !== str2[i]) {
break;
}
}
return str1.substring(0, i);
};
const compareTwo_plus = function(str1, str2) {
let result = "";
for (let i = 0; i < str1.length && i < str2.length; i++) {
if (str1[i] !== str2[i]) {
break;
}
result += str1[i];
}
return result;
};
var longestCommonPrefix = function(strs) {
if (strs.length == 0) {
return "";
}
let result = strs[0];
for (let i = 1; i < strs.length; i++) {
result = compareTwo_plus(result, strs[i]);
// result = compareTwo_minus(result, strs[i]);
if (result === "") { // 如果有一个是""，就直接输出结果
break;
}
}
return result;
};
减法：
Runtime: 52 ms, faster than 95.14% of JavaScript online submissions forLongest Common Prefix.
Memory Usage: 35 MB, less than 61.97% of JavaScript online submissions for Longest Common Prefix.
加法：
Runtime: 52 ms, faster than 95.14% of JavaScript online submissions forLongest Common Prefix.
Memory Usage: 36.7 MB, less than 8.39% of JavaScript online submissions for Longest Common Prefix.
两者好像差不多。。
两分法
把strs数组，不断从中间切两半。切到两个元素一组，再用$LCP(S_1,S_2) $来比较。
感觉这和一个个找没啥本质区别，反而逻辑更复杂了。。。
还有个两分查找法
没能复现出来。。
字典树也复现不出来。。
