14.最长公共前缀

LeetCode

需要注意的坑

• 公共的意思是数组中所有项公共的部分，["aa",'aabb','aabbcc'],最长公共前缀是aa,而不是aabb,因为并不是每一项都包含aabb

• 最长公共前缀而不是最长公共子串，["xbbcc","xaabbcc","xbbccdd"],最长公共前缀是x,最长公共子串 bbcc

• 在输入的数组长度为0时返回空字符串

1.纵向扫描

纵向扫描是最容易想到的方法步骤为：

• 依次遍历每一个数组，检查同一列上的字符是否相同
• 如果相同记录并累加字符串结果，遍历下一列
• 如果不同跳出循环，返回结果

var longestCommonPrefix = function (strs) {
    if (!strs.length) return '';
    var result = '', //记录公共前缀结果
        i = 0, //表示字符串索引，从第一位开始检查
        j = 1, // 输入数组的索引
        str = strs[0]; //输入数组中的第一个
    for (i = 0; i < str.length; i++) {
        for (j = 1; j < strs.length; j++) {
            if (strs[j][i] !== str[i]) return result;
        }
        result += str[i]
    }
    return result;
}

复杂度分析

• 时间复杂度：，其中 是字符串数组中的字符串的平均长度， 是字符串的数量。最坏情况下，字符串数组中的每个字符串的每个字符都会被比较一次。

• 空间复杂度：。使用的额外空间复杂度为常数。

2.横向扫描

• 依次遍历字符串数组中的每个字符串，把前两个公共前缀的结果和输入数组中的下一个进行比较，数组遍历完成后即得到结果
• 如果在尚未遍历完所有的字符串时，最长公共前缀已经是空串，则最长公共前缀一定是空串，因此不需要继续遍历剩下的字符串，直接返回空串即可。

var longestCommonPrefix = function (strs) {
    if (!strs.length) return '';
    var i = 0,
        len = strs.length - 1,
        result = strs[0];
    for (; i < len; i++) {
        var temp = prefixCompare(result, strs[i + 1]);
        if(!temp) return temp;
        result = temp;
    }
    return result;
}
// 找出两个字符串的最大公共前缀
function prefixCompare(first, second) {
    var i = 0, //索引
        len = first.length;
    for (; i < len; i++) {
        if (first[i] !== second[i]) return first.substring(0, i);
    }
    return first;
}

复杂度分析

• 时间复杂度：O(mn)，其中 mm 是字符串数组中的字符串的平均长度，nn 是字符串的数量。最坏情况下，字符串数组中的每个字符串的每个字符都会被比较一次。

• 空间复杂度：O(1)。使用的额外空间复杂度为常数。

3.分治

注意到 的计算满足结合律，有以下结论：

其中是字符串的最长公共前缀，

基于上述结论，可以使用分治法得到字符串数组中的最长公共前缀。对于问题 可以分解成两个子问题,与,其中。对两个子问题分别求解，然后对两个子问题的解计算最长公共前缀，即为原问题的解。

var longestCommonPrefix = function (strs) {
    if (!strs.length) return '';
    if (strs.length < 2) return strs[0];
    var mid = Math.floor(strs.length / 2),
        left = strs.slice(0, mid),
        right = strs.slice(mid);
    return prefixCompare(longestCommonPrefix(left), longestCommonPrefix(right))
}

// 找出两个字符串的最大公共前缀
function prefixCompare(first, second) {
    var i = 0, //索引
        len = first.length;
    for (; i < len; i++) {
        if (first[i] !== second[i]) return first.substring(0, i);
    }
    return first;
}

复杂度分析

• 时间复杂度：O(mn)，其中 mm 是字符串数组中的字符串的平均长度，nn 是字符串的数量。

• 空间复杂度：，其中 mm 是字符串数组中的字符串的平均长度，nn 是字符串的数量。空间复杂度主要取决于递归调用的层数，层数最大为 ，每层需要 m 的空间存储返回结果。

4.二分法

显然，最长公共前缀的长度不会超过字符串数组中的最短字符串的长度。用 minLength 表示字符串数组中的最短字符串的长度，则可以在 [0,minLength] 的范围内通过二分查找得到最长公共前缀的长度。每次取查找范围的中间值 mid，判断每个字符串的长度为 mid 的前缀是否相同，如果相同则最长公共前缀的长度一定大于或等于 mid，如果不相同则最长公共前缀的长度一定小于 mid，通过上述方式将查找范围缩小一半，直到得到最长公共前缀的长度。

var longestCommonPrefix = function (strs) {
    if (!strs.length) return '';
    var minlength = Math.min.apply(null, strs.map(item => item.length)),
        low = 0,
        high = minlength;
    while (low < high) {
        var mid = ~~((high - low + 1) / 2 + low);
        if (prefixCompare(strs, mid)) {
            low = mid;
        } else {
            high = mid - 1;
        }
    }
    return strs[0].substring(0, low);
}

function prefixCompare(strs, mid) {
    var str0 = strs[0].substring(0, mid);
    var count = strs.length;
    for (var i = 1; i < count; i++) {
        var str = strs[i];
        for (var j = 0; j < mid; j++) {
            if (str0[j] != str[j]) {
                return false;
            }
        }
    }
    return true;
}

复杂度分析

• 时间复杂度：，其中 mm 是字符串数组中的字符串的最小长度，nn 是字符串的数量。二分查找的迭代执行次数是 ，每次迭代最多需要比较 个字符，因此总时间复杂度是 .

• 空间复杂度：。使用的额外空间复杂度为常数。

打赏