leetcode 刷题记：14. 最长公共前缀

看起来很简单的一道题，时间复杂度居然是$O(n^2)$

问题描述

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

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

// @algorithm @lc id=14 lang=javascript 
// @title longest-common-prefix
// @test(["flower","flow","flight"])="fl"
// @test(["dog","racecar","car"])=""

解题思路

方案有很多，最简单的有两个种：

1. 对所有字符串的第 x 位对比，每一次遍历对比相等就把该位字符累加到result上。只要遍历对比失败则返回result。
2. $0<n<arr.length-2$，第 1 个字符串与第 n 个字符串按位对比。更新最长字符前缀到arr第 1 个元素。当最长前缀为""则推出遍历，返回""，或者数组遍历完成，返回数组第一个的元素。

方案一

代码:

/**
 * @param {string[]} strs
 * @return {string}
 */
const longestCommonPrefix = function(strs) {
    let res = "";
    let t = "";
    for (let index = 0; index < strs[0].length; index++) {
        t = strs[0][index];
        for (let j = 1; j < strs.length; j++) {
            if (t !== strs[j][index]) {
                return res;
            }
        }
        res += t;
    }
    return res;
};

方案二

代码:

/**
 * @param {string[]} strs
 * @return {string}
 */
const longestCommonPrefix = function(strs) {
    if (!strs.length || !strs[0].length) {
        return "";
    }
    for (let i = 0; i < strs.length - 1; i++) {
        let result = "";
        for (let j = 0; j <= strs[i].length - 1; j++) {
            if (strs[0][j] !== strs[i + 1][j]) {
                strs[0] = result;
                break;
            } else {
                result += strs[0][j];
            }
        }
    }
    return strs[0];
};

方案三

前面两者办法都是循环嵌套。有没有更 hack 的方式？用字符串比大小，获取出数组中字母排序最前与字母排序最后的两个元素获取最长子串。

/**
 * @param {string[]} strs
 * @return {string}
 */
const longestCommonPrefix = function(strs) {
    if (strs.length === 0) return "";
    let minStr = strs[0];
    let maxStr = "";
    for (let i = 0; i < strs.length; i++) {
        if (strs[i] < minStr) minStr = strs[i];
        if (strs[i] > maxStr) maxStr = strs[i];
    }
    let result = "";
    for (let j = 0; j < minStr.length; j++) {
        if (minStr[j] !== maxStr[j]) return result;
        result += minStr[j];
    }
    return result;
};