14. 最长公共前缀

[funnycoderstar]

JavaScript实现Leetcode 14. 最长公共前缀

题目描述

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

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

示例 1:

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

示例 2:

输入: ["dog","racecar","car"]
输出: ""

解释: 输入不存在公共前缀。
说明:

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

解析思路

1. 字符串数组长度为0时，公共前缀为空，直接返回
2. 初始化公共前缀 commonPrefix 为 第一个字符串
3. 遍历后面的字符串依次和 commonPrefix 进行比较，两两找出公共前缀，最终结果即为 最长公共前缀

解题方法

/**
 * @param {string[]} strs
 * @return {string}
 * 1. commonPrefix为 flower
 * 2. 比较 flower和flow，相同的值为 fl
 * 3. 比较 fl 和 flight，形同的值为 fl
 * 如何比较 flower和flow: c使用for循环，一个字符一个字符的比较
 */
var longestCommonPrefix = function(strs) {
    if(!strs.length) {
        return '';
    }
    let common = '';
    // 第一个字符串为初始值
    let commonPrefix = strs[0];
    for(let i = 0 ; i < commonPrefix.length; i++) {
        // 遍历strs中剩下的 的值
        for(let j = 1; j < strs.length; j++) {
            // 每一个都和 commonPrefix 比较，找到公共的部分，否则返回 common
            if(commonPrefix[i] !== strs[j][i]) {
                return common;
            }
        }
        common += commonPrefix[i];
    }
    return common;
};

• 时间复杂度： O(n)，n为所有字符串长度之和
• 空间复杂度： O(1)，使用常量来存储变量