每天一道力扣题：14. 最长公共前缀

题目

编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 ""。 示例 1: **

输入: ["flower","flow","flight"]
输出: "fl"

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

思路

水平扫描

这里的水平扫描指的是从后往前扫描字符的每一列。

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    // 先处理边界情况
    if (!strs || !strs.length || !Array.isArray(strs)) return ''
    // 默认第一个作为最长公共前缀
    let prefix = strs[0]
    for (let i = 1; i < strs.length; i++) {
        // 不断寻找最长公共前缀, 注意指的是[前缀],审题要清
        const curStr = strs[i]
        while(curStr.indexOf(prefix) !== 0) {
            prefix = prefix.substring(0, prefix.length - 1)
            if (!prefix) return ''
        }
    }
    return prefix
};

时间复杂度：O(S)，S为strs中每个字符的总和。空间复杂度：O(1)。

进阶版水平扫描

前面那种算法存在一个问题，假设数组默认存在一个最短字符串s，那么上面的算法会将s前面所有的字符都扫描一遍。

那么我们的优化策略是改为从前往后扫描字符串的每一列。

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    // 先处理边界情况
    if (!strs || !strs.length || !Array.isArray(strs)) return ''
    const start = strs[0]
    for (let i = 0; i < start.length; i++) {
        const char = start[i]
        for (let j = 1; j < strs.length; j++) {
            // 先比较i === strs[j].length 可以跳过后面不必要字符比较
            // 再比较每个字符串相同位置的字符
            if (i === strs[j].length || char !== strs[j][i]) {
                return start.substring(0, i)
            }
        }
    }
    // 默认第一个是最短的、也就是最长的公共前缀
    return start
};

时间复杂度：O(S)。最坏情况时间复杂度就是出现n个长度都为m的字符串，那么会进行nm次对比，因为我们是对每字符进行比较。但是最好情况时间复杂度是nmin(m)，即取决于最短的那个字符串长度。空间复杂度：O(1)。

分治

通过分治技巧，把大规模的同等问题不断拆成小规模，最后对小规模问题进行求解。

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    // 先处理边界情况
    if (!strs || !strs.length || !Array.isArray(strs)) return ''
    return splitLongestPrefix(strs, 0, strs.length-1)

    function splitLongestPrefix(strs, left, right) {
        // 跳出递归的终止条件：左、右指针相等，即不能再拆
        if (left === right) {
            return strs[left]
        }
        const mid = Math.floor((left+right)/2)
        const leftStr = splitLongestPrefix(strs, left, mid)
        const rightStr = splitLongestPrefix(strs, mid + 1, right)
        // 拆到最小后，两两比较
        return commonPrefix(leftStr, rightStr)
    }
    function commonPrefix(leftStr, rightStr) {
        // 两两比较还是通过相同索引位置比较单个字符
        // 先取长度最短的作为base
        const minLength = Math.min(leftStr.length, rightStr.length)
        for (let i = 0; i < minLength; i++) {
            if (leftStr[i] !== rightStr[i]) {
                return leftStr.substring(0, i)
            }
        }
        return leftStr.substring(0, minLength)
    }
};

最坏情况下： n个长度为m的相同字符串时间复杂度O(S)，S=mn。空间复杂度O(mlogn)。

二分查找法

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    // 先处理边界情况
    if (!strs || !strs.length || !Array.isArray(strs)) return ''
    // 先找出strs中最短的字符串，即也是潜在可能的最长字符串
    let minStrLen = Number.MAX_SAFE_INTEGER;
    strs.map(str => {
        minStrLen = Math.min(minStrLen, str.length)
    })
    // 对潜在可能的最长字符串进行二分查找
    let left = 1
    let right = minStrLen
    // 需要注意二分的终止条件
    while(left <= right) {
        let mid = Math.floor((left+right)/2)
        if (isStartWithCommonStr(strs, mid)) {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    function isStartWithCommonStr(strs, mid) {
        let commonStr = strs[0].substring(0, mid)
        for (let i = 1; i < strs.length; i++) {
            if (!strs[i].startsWith(commonStr)) {
                return false
            }
        }
        return true
    }
    return strs[0].substring(0, Math.floor((left+right)/2))
};

最坏情况下： n个长度为m的相同字符串时间复杂度O(Slogn)，logn是二分迭代次数，S = mn。空间复杂度O(1)。

广告位

觉得有意思点个右下角在看，或者直接关注。