最长公共前缀

题目描述

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

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

示例

示例 1：

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

示例 2：

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

约束条件

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i] 仅由小写英文字母组成（如果非空）

我的解题过程

方法一：排序后纵向扫描

先找到最短的字符串作为参考，然后逐个下标比较所有字符串在该位置的字符，如果有一个不相等就停止并返回结果。

function longestCommonPrefix(strs: string[]): string {
  let sortArr = strs.sort((a, b) => a.length - b.length);
  const minStr = sortArr[0];
  const restArr = sortArr.slice(1);

  let res = "";
  for (let i = 0; i < minStr.length; i++) {
    const isPass = restArr.every((v) => minStr[i] === v[i]);
    if (!isPass) break;

    res += minStr[i];
  }

  return res;
}

方法二：直接纵向扫描

如果按照上述思路，其实不需要排序，只需要以第一个字符串作为参照物即可。这样可以避免排序的时间开销。

function longestCommonPrefix(strs: string[]): string {
  const flag = strs[0];
  let res = "";

  for (let i = 0; i < flag.length; i++) {
    const isPass = strs.every((v) => flag[i] === v[i]);
    if (!isPass) break;

    res += flag[i];
  }

  return res;
}

解题思路

核心逻辑：

要找到所有字符串的公共前缀，关键在于纵向比较每个位置的字符：

1. 选择一个字符串作为参考（可以是第一个或最短的）
2. 从第一个字符开始，纵向扫描所有字符串的相同位置
3. 如果所有字符串在当前位置的字符都相同，则该字符是公共前缀的一部分
4. 一旦出现不匹配的字符或任一字符串到达末尾，立即停止并返回已找到的公共前缀

算法步骤：

1. 选择第一个字符串作为参考字符串
2. 遍历参考字符串的每个字符位置 i
3. 使用 every() 方法检查所有字符串在位置 i 的字符是否都相同
4. 如果都匹配，将该字符添加到结果中；否则终止循环
5. 返回累积的结果字符串