005-最长公共前缀 (Longest Common Prefix)

题目描述

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

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

示例

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

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

解题思路

使用垂直扫描法，比较所有字符串在同一位置的字符。从第一个字符开始，逐位比较所有字符串，直到找到不匹配的字符或到达某个字符串的末尾。

JavaScript 解决方案

/**
 * @param {string[]} strs
 * @return {string}
 */
const longestCommonPrefix = (strs) => {
    if (strs.length === 0) return "";
    if (strs.length === 1) return strs[0];
    
    let prefix = "";
    const firstStr = strs[0];
    
    // 遍历第一个字符串的每个字符
    for (let i = 0; i < firstStr.length; i++) {
        const char = firstStr[i];
        
        // 检查其他字符串在相同位置是否有相同的字符
        for (let j = 1; j < strs.length; j++) {
            if (i >= strs[j].length || strs[j][i] !== char) {
                return prefix;
            }
        }
        
        prefix += char;
    }
    
    return prefix;
};

复杂度分析

时间复杂度：O(S)，其中 S 是所有字符串中字符数量的总和
空间复杂度：O(1)，只使用了常数额外空间

测试用例

// 测试函数
const testLongestCommonPrefix = () => {
    const testCases = [
        {
            strs: ["flower", "flow", "flight"],
            expected: "fl"
        },
        {
            strs: ["dog", "racecar", "car"],
            expected: ""
        },
        {
            strs: ["interspecies", "interstellar", "interstate"],
            expected: "inters"
        },
        {
            strs: ["throne", "throne"],
            expected: "throne"
        },
        {
            strs: ["a"],
            expected: "a"
        },
        {
            strs: [],
            expected: ""
        },
        {
            strs: ["", "b"],
            expected: ""
        },
        {
            strs: ["aa", "a"],
            expected: "a"
        }
    ];

    testCases.forEach((testCase, index) => {
        const result = longestCommonPrefix(testCase.strs);
        const passed = result === testCase.expected;
        console.log(`测试用例 ${index + 1}: ${passed ? '通过' : '失败'}`);
        console.log(`输入: strs = [${testCase.strs.map(s => `"${s}"`).join(', ')}]`);
        console.log(`期望: "${testCase.expected}", 实际: "${result}"\n`);
    });
};

// 运行测试
testLongestCommonPrefix();

关键点总结

边界情况：空数组、单个字符串、空字符串的处理
垂直扫描：逐位比较所有字符串的相同位置字符
提前返回：一旦发现不匹配就立即返回当前前缀
字符串长度：注意处理字符串长度不同的情况
字符比较：使用严格相等比较字符

总结

这道题考察了以下重点：

字符串处理：如何高效地比较多个字符串
数组遍历：处理字符串数组的技巧
边界处理：对各种边界情况的考虑
算法优化：使用垂直扫描法提高效率

垂直扫描法是最优解，时间复杂度为 O(S)，空间复杂度为 O(1)。在实际面试中，建议先考虑边界情况，然后实现核心算法。

005-最长公共前缀 (Longest Common Prefix)

On this page