查找数组公共前缀（美团）

问题

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

例如：

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

解答

/**
 * 查找字符串数组的最长公共前缀
 * @param {string[]} strs - 字符串数组
 * @return {string} - 最长公共前缀
 */
function longestCommonPrefix(strs) {
  // 边界情况处理
  if (!strs || strs.length === 0) {
    return '';
  }
  
  // 只有一个字符串时，直接返回该字符串
  if (strs.length === 1) {
    return strs[0];
  }
  
  // 以第一个字符串为基准
  let prefix = strs[0];
  
  // 遍历剩余的字符串
  for (let i = 1; i < strs.length; i++) {
    // 当前字符串不以 prefix 开头时，缩短 prefix
    while (strs[i].indexOf(prefix) !== 0) {
      // 去掉 prefix 的最后一个字符
      prefix = prefix.substring(0, prefix.length - 1);
      
      // 如果 prefix 为空，说明没有公共前缀
      if (prefix === '') {
        return '';
      }
    }
  }
  
  return prefix;
}

// 方法二：纵向扫描（逐字符比较）
function longestCommonPrefix2(strs) {
  if (!strs || strs.length === 0) {
    return '';
  }
  
  // 以第一个字符串的长度为基准
  for (let i = 0; i < strs[0].length; i++) {
    const char = strs[0][i];
    
    // 检查其他字符串的第 i 个字符是否与 char 相同
    for (let j = 1; j < strs.length; j++) {
      // 如果某个字符串长度不够，或字符不匹配
      if (i >= strs[j].length || strs[j][i] !== char) {
        return strs[0].substring(0, i);
      }
    }
  }
  
  // 第一个字符串就是公共前缀
  return strs[0];
}

// 方法三：分治法
function longestCommonPrefix3(strs) {
  if (!strs || strs.length === 0) {
    return '';
  }
  
  return divideAndConquer(strs, 0, strs.length - 1);
}

function divideAndConquer(strs, left, right) {
  // 只有一个字符串
  if (left === right) {
    return strs[left];
  }
  
  // 分治
  const mid = Math.floor((left + right) / 2);
  const leftPrefix = divideAndConquer(strs, left, mid);
  const rightPrefix = divideAndConquer(strs, mid + 1, right);
  
  // 合并：找出两个前缀的公共部分
  return commonPrefix(leftPrefix, rightPrefix);
}

function commonPrefix(str1, str2) {
  const minLength = Math.min(str1.length, str2.length);
  for (let i = 0; i < minLength; i++) {
    if (str1[i] !== str2[i]) {
      return str1.substring(0, i);
    }
  }
  return str1.substring(0, minLength);
}

使用示例

// 示例 1：存在公共前缀
const strs1 = ["flower", "flow", "flight"];
console.log(longestCommonPrefix(strs1)); // 输出: "fl"

// 示例 2：不存在公共前缀
const strs2 = ["dog", "racecar", "car"];
console.log(longestCommonPrefix(strs2)); // 输出: ""

// 示例 3：完全相同的字符串
const strs3 = ["test", "test", "test"];
console.log(longestCommonPrefix(strs3)); // 输出: "test"

// 示例 4：空数组
const strs4 = [];
console.log(longestCommonPrefix(strs4)); // 输出: ""

// 示例 5：只有一个字符串
const strs5 = ["alone"];
console.log(longestCommonPrefix(strs5)); // 输出: "alone"

// 使用方法二
console.log(longestCommonPrefix2(["flower", "flow", "flight"])); // 输出: "fl"

// 使用方法三
console.log(longestCommonPrefix3(["flower", "flow", "flight"])); // 输出: "fl"

关键点

• 边界条件处理：需要考虑空数组、单个字符串等特殊情况

• 横向扫描法（方法一）：以第一个字符串为基准，依次与后续字符串比较，不断缩短前缀直到匹配。时间复杂度 O(S)，S 为所有字符串的字符总数

• 纵向扫描法（方法二）：逐列比较所有字符串的每个字符，一旦发现不匹配立即返回。适合公共前缀较短的场景，可以提前终止

• 分治法（方法三）：将数组分成两部分，分别求公共前缀，再合并结果。时间复杂度 O(S)，但递归调用栈深度为 O(log n)

• indexOf 的妙用：str.indexOf(prefix) !== 0 可以判断字符串是否以某个前缀开头

• 性能优化：可以先找出最短字符串，以其长度为上限进行比较，避免不必要的遍历