JavaScript查找字符串数组最长公共前缀的字符排序问题求解

需求描述 #

从字符串数组中查找所有字符串共享的最长公共前缀，示例输入["flower","flow","flight"]的预期输出为"fl"。

现有代码及问题 #

第一版代码 #

var longestCommonPrefix = function(strs) {
    strs.forEach((item, index) => {
      let splitArr = item.split('');
      console.log('split array item is: ' + splitArr)
    });
};

longestCommonPrefix(["flower","flow","flight"])

该代码输出为各字符串拆分后的字符数组：

split array item is: f,l,o,w,e,r 
split array item is: f,l,o,w 
split array item is: f,l,i,g,h,t

第二版代码及问题 #

调整后的代码尝试把所有字符存入同一数组后统计：

var longestCommonPrefix = function(strs) {
    // 定义新数组用于存储所有字符
    // 定义在循环外侧，便于后续排序、统计
    let charArray = [];
      
    // 遍历每个字符串
    strs.forEach((item, index) => {
      // 将字符串按字符拆分
      let splitArr = item.split('');
      // 测试日志
      console.log('split array item is: ' + splitArr)
      // 遍历每个字符，推入新数组
      splitArr.forEach((letter, index) => {
        charArray.push(letter)
      });
    });
    // 打印最终数组
    console.log('FINAL ARRAY IS...: ' + charArray)
};

longestCommonPrefix(["flower","flow","flight"])

该代码得到的是一维平铺的字符数组f,l,o,w,e,r,f,l,o,w,f,l,i,g,h,t，调用sort()后得到按字典序排序的结果，无法达成「按字符位置分组」的需求。

推荐搜索关键词 #

你可以用以下关键词搜索相关实现方案：

• JavaScript 字符串数组按字符位置分组
• JS 二维数组按列遍历
• 最长公共前缀 逐位匹配实现

按位置分组的实现方案 #

你当前的问题是将所有字符按字符串维度（行）平铺，要得到按位置（列）分组的序列，需要优先遍历字符位置，再遍历所有字符串取对应位置的字符，修正后的完整实现如下：

var longestCommonPrefix = function(strs) {
    // 边界处理：空数组直接返回空串
    if(strs.length === 0) return "";
    // 公共前缀最长不会超过数组中最短字符串的长度
    const minStrLength = Math.min(...strs.map(str => str.length));
    let commonPrefix = "";

    // 按字符位置（列）遍历
    for(let pos = 0; pos < minStrLength; pos++) {
        // 取第一个字符串的当前位置字符为基准
        const baseChar = strs[0][pos];
        // 检查所有字符串当前位置字符是否一致
        const isAllSame = strs.every(str => str[pos] === baseChar);
        if(isAllSame) {
            commonPrefix += baseChar;
        } else {
            // 出现不一致直接终止遍历，返回已匹配的前缀
            break;
        }
    }
    return commonPrefix;
};

// 测试调用
console.log(longestCommonPrefix(["flower","flow","flight"])) // 输出 "fl"

如果需要单独生成你期望的按位置分组的字符序列，可以加入以下逻辑：

const groupedChars = [];
for(let pos = 0; pos < minStrLength; pos++) {
    for(let i = 0; i < strs.length; i++) {
        groupedChars.push(strs[i][pos]);
    }
}
console.log(groupedChars); // 输出 ["f","f","f","l","l","l","o","o","i","w","w","g"]

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