LeetCode-14-最长公共前缀

字符串

原题地址：最长公共前缀

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

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

示例 1:

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

示例 2:

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

说明:

所有输入只包含小写字母 a-z 。

暴力解法

因为公共前缀必须是数组中每一个字符串的前缀，所以我们可以将最长前缀初始化为第一个字符串，然后遍历数组来不断缩短这个最长前缀，就可以找到最后的结果：

/**
 * @param {string[]} strs
 * @return {string}
 */
const longestCommonPrefix1 = function(strs) {
    if (strs.length < 1) {
        return ''
    }

    /**
     * 寻找两个字符串的公共前缀
     * @param str1 字符串1
     * @param str2 字符串2
     * @returns {string|*} 公共前缀
     */
    const findCommonPrefix = (str1, str2) => {
        for (let i = 0; i < Math.min(str1.length, str2.length); i ++) {
            if (str1[i] !== str2[i]) {
                return i === 0 ? '' : str1.substr(0, i);
            }
        }
        return str1.length < str2.length ? str1 : str2;
    };

    // 初始化为第一个字符串
    let result = strs[0];
    // 通过遍历来缩小公共前缀的长度
    for (let i = 1; i < strs.length; i++) {
        result = findCommonPrefix(result, strs[i]);
        // 如果找到的前缀已经是空串了，结果一定是空串，可以直接返回
        if (result.length === 0) {
            return '';
        }
    }

    return result;
};

测试：

let start = new Date();
const test = longestCommonPrefix1;
console.log(test(['flower', 'flow', 'flight'])); // fl
console.log(test(['dog', 'racecar', 'car'])); // 返回空字符串
console.log(test([])); // 返回空字符串
console.log(new Date().getTime() - start.getTime()); // 3

时间复杂度： 时间复杂度为O(n)，n是所有输入字符的数量，最差情况下需要把所有的输入字符都比较一次
空间复杂度： 只需要固定数量的额外空间，空间复杂度为O(1)

本文由 李海平 创作，采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Jul 28,2019