关于leetcode:leetcode-算法练习-14-最长公共前缀

题目

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

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

• 示例 1：

 输出：strs = ["flower","flow","flight"]
输入："fl"

• 示例 2：

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

• 提醒：

1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] 仅由小写英文字母组成 

地址

leetcode 题目地址

刷题源码地址

纵向扫描

找到 strs 中最短的字符串，循环最短长度，每一遍比照每一个的字符的第一个、第二个 … 字符是否相等，如果不想等，间接返回；循环完结，找到公共前缀（如果循环没有提前退出，也就是最短字符串为公共前缀）。

export function longestCommonPrefix(strs: string[]): string {
  let j = 0;
  let prefix = "";
  let minLength = Math.min(...strs.map((v) => v.length));

  while (minLength > 0) {prefix += strs[0][j];
    for (let i = 0; i < strs.length; i++) {if (strs[i][j] !== prefix[j]) {return prefix.slice(0, j);
      }
    }
    j++;
    minLength--;
  }

  return prefix;
}

工夫复杂度是 O(mn)，m 是字符串数量，n 是最短字符串长度 +2。

• 精简优化代码

取第一个字符串做 prefix，进行比照，遇到不同字符返回 0～j 下标地位的字符串；

不须要计算最短长度，因为当某个字符串的字符取不到的时候就会触发返回条件了。

export function longestCommonPrefix1(strs: string[]): string {let prefix = strs[0];
  for (let j = 0; j < prefix.length; j++) {for (let i = 1; i < strs.length; i++) {if (strs[i][j] !== prefix[j]) {return prefix.slice(0, j);
      }
    }
  }
  return prefix;
}

横向搜寻

取两个字符串，找出它们的公共前缀，再用此前缀持续和前面的字符串找公共前缀

export function longestCommonPrefix(strs: string[]): string {let prefix = strs[0];
  for (let i = 1; i < strs.length; i++) {prefix = commonPrefix(prefix, strs[i]);
    if (!prefix) break;
  }
  function commonPrefix(str1: string, str2: string) {
    let j = 0;
    while (j < str1.length && str1[j] == str2[j]) j++;
    return str1.slice(0, j);
  }
  return prefix;
}