字符串最长公共前缀

问题

编写一个函数，查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 ""。

示例：

• 输入：["flower", "flow", "flight"]，输出："fl"
• 输入：["dog", "racecar", "car"]，输出：""

解答

方法一：横向扫描

依次比较相邻字符串，逐步缩小公共前缀。

function longestCommonPrefix(strs) {
  // 空数组直接返回
  if (strs.length === 0) return "";
  
  // 以第一个字符串作为初始前缀
  let prefix = strs[0];
  
  // 依次与后面的字符串比较
  for (let i = 1; i < strs.length; i++) {
    // 不断缩短前缀，直到匹配
    while (strs[i].indexOf(prefix) !== 0) {
      prefix = prefix.slice(0, -1);
      // 前缀为空，说明没有公共前缀
      if (prefix === "") return "";
    }
  }
  
  return prefix;
}

// 测试
console.log(longestCommonPrefix(["flower", "flow", "flight"])); // "fl"
console.log(longestCommonPrefix(["dog", "racecar", "car"]));    // ""

方法二：纵向扫描

逐列比较所有字符串的同一位置字符。

function longestCommonPrefix(strs) {
  if (strs.length === 0) return "";
  
  // 遍历第一个字符串的每个字符
  for (let i = 0; i < strs[0].length; i++) {
    const char = strs[0][i];
    
    // 检查其他字符串同一位置的字符
    for (let j = 1; j < strs.length; j++) {
      // 超出长度或字符不匹配
      if (i >= strs[j].length || strs[j][i] !== char) {
        return strs[0].slice(0, i);
      }
    }
  }
  
  // 第一个字符串本身就是公共前缀
  return strs[0];
}

方法三：排序后比较首尾

排序后只需比较第一个和最后一个字符串。

function longestCommonPrefix(strs) {
  if (strs.length === 0) return "";
  if (strs.length === 1) return strs[0];
  
  // 字典序排序
  strs.sort();
  
  const first = strs[0];
  const last = strs[strs.length - 1];
  let i = 0;
  
  // 比较首尾字符串
  while (i < first.length && first[i] === last[i]) {
    i++;
  }
  
  return first.slice(0, i);
}

关键点

• 横向扫描：时间 O(S)，S 为所有字符总数，空间 O(1)
• 纵向扫描：遇到不匹配立即返回，适合公共前缀较短的情况
• 排序法：排序后首尾字符串差异最大，只需比较它们
• 边界处理：空数组、单元素数组、空字符串
• 实际应用：自动补全、文件路径处理、URL 匹配