寻找匹配数组超50%元素的最长前缀问题及代码优化咨询

现有字符串数组["apple", "ape", "application", "item"]，需找出能匹配数组中超过50%元素的最长公共前缀。示例中"ap"匹配3个元素（共4个），符合要求应返回该前缀。

以下是我的尝试代码：

const longestPrefix = (arrStr) => {
  if (arrStr.length === 0) return "";

  let prefix = "";
  let noPrefixMatched = {};
  // loop the characters of first word
  for (let i = 0; i < arrStr[0].length; i++) {
    let char = arrStr[0][i];
    let j = 0;
    // loop all the words of the array except first one
    for (j = 1; j < arrStr.length; j++) {
      if (arrStr[j][i] !== char) {
        // if first char not matched then set that word as notMatched
        if (i === 0) {
          noPrefixMatched[arrStr[j]] = true;
        }
        break;
      }
      // if the first characters are equal in all words and the loop reach the final word
      if (arrStr[j][i] === char && j === arrStr.length - 1) {
        prefix += char;
      }
    }
  }

  return prefix;
};

我采用纵向对比法获取最常见前缀，但当数组中存在无匹配前缀的元素（如"item"）时无法正常运行，该如何解决？

问题分析 #

原代码的核心逻辑完全没贴合“匹配超过50%元素”的需求：它仅在所有其他字符串都匹配当前字符时才追加前缀，一旦遇到不匹配的元素就中断遍历，既没统计匹配该前缀的元素数量，也没考虑允许部分元素不匹配的情况，自然处理不了像"item"这种完全不匹配基准字符串的元素。

解决方案 #

我们需要先统计所有可能前缀的匹配次数，再筛选出符合条件的最长前缀。具体实现如下：

实现代码 #

const longestPrefix = (arrStr) => {
  if (arrStr.length === 0) return "";
  
  // 计算匹配阈值：超过数组长度的50%
  const threshold = arrStr.length / 2;
  // 用Map统计每个前缀的匹配次数
  const prefixCount = new Map();
  // 找出最短字符串的长度，限制前缀最大可能长度，优化性能
  const maxPrefixLen = Math.min(...arrStr.map(str => str.length));
  
  // 遍历每个字符串，生成所有可能的前缀并统计次数
  for (const str of arrStr) {
    for (let i = 1; i <= maxPrefixLen; i++) {
      const prefix = str.slice(0, i);
      prefixCount.set(prefix, (prefixCount.get(prefix) || 0) + 1);
    }
  }
  
  let longestValidPrefix = "";
  // 遍历统计结果，筛选出符合条件的最长前缀
  for (const [prefix, count] of prefixCount.entries()) {
    if (count > threshold && prefix.length > longestValidPrefix.length) {
      longestValidPrefix = prefix;
    }
  }
  
  return longestValidPrefix;
};

// 测试示例
console.log(longestPrefix(["apple", "ape", "application", "item"])); // 输出 "ap"

代码说明 #

1. 阈值计算：以数组长度的一半为基准，匹配次数超过该值的前缀才符合要求。
2. 前缀统计：遍历每个字符串，生成它的所有可能前缀（长度从1到最短字符串长度），用Map记录每个前缀被多少个字符串匹配。
3. 筛选最长前缀：遍历统计结果，找出匹配次数达标且长度最长的前缀。

这种方法不受数组中是否存在完全不匹配元素的影响，能准确统计所有前缀的匹配情况，最终得到符合要求的结果。

内容的提问来源于stack exchange，提问作者nekoroden