8-最长公共前缀

题目

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

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

示例 1:

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

示例 2:

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

说明:

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

解答

竖直扫描

一个个元素拿出来，一起比较他们的某个指针对应的字符。

累加双循环

外层设置一个index指针，一个个数组元素来比较index上的字符。

• 如果每个数组元素的index字符都一样，那么就加入到result当中；

• 如果有一个不一样，那么就直接return结果；

• 或者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

链接：https://leetcode-cn.com/problems/two-sum/solution/hua-jie-suan-fa-14-zui-chang-gong-gong-qian-zhui-b/

思路是，先随便初始化一个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) $来比较。

image-20190701153804080

感觉这和一个个找没啥本质区别，反而逻辑更复杂了。。。

还有个两分查找法

image-20190701161103988

没能复现出来。。

字典树也复现不出来。。