阅读 49

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

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

题目

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

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

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

思路

水平扫描

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

屏幕快照 2020-04-22 下午10.21.34.png

/**
 * @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)。

分治

屏幕快照 2020-04-23 上午8.34.07.png
通过分治技巧,把大规模的同等问题不断拆成小规模,最后对小规模问题进行求解。

/**
 * @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)。

二分查找法

屏幕快照 2020-04-25 上午11.02.40.png

/**
 * @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)。

广告位

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

qrcode_for_gh_1f177110559d_430.jpg

关注下面的标签,发现更多相似文章
评论