014.最长公共前缀.md

题目描述

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

示例

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

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

思路

• 初始字符串为第一个字符串，逐个扫描后面的字符串找到公共前缀
• 逐个扫描各个字符串对应位置的字符，比较是否连续相等

代码

/**
 * @param {string[]} strs
 * @return {string}
 */
let longestCommonPrefix = function(strs) {
    if (!strs || strs.length === 0) {
        return '';
    }
    // 以第一个字符串为默认公关前缀
    let prefix = strs[0];
    for (let i = 1, l = strs.length; i < l; i++) {
        let j = prefix.length;
        while (j >= 0) {
            // 查找与strs[i]的公关前缀
            let substr = strs[i].substr(0, j)
            if (prefix === substr) {
                prefix = substr;
                break;
            }
            // 不匹配则从末尾去除一个字符，继续匹配
            else {
                j--;
                prefix = prefix.substr(0, j);
            }
        }
    }
    return prefix;
};

/**
 * @param {string[]} strs
 * @return {string}
 */
let longestCommonPrefix = function(strs) {
    if (!strs || strs.length === 0) {
        return '';
    }
    // 以第一个字符串为准，遍历所有字符，查找满足其他所有字符串的公关前缀
    for (let i = 0, l = strs[0].length; i < l; i++) {
        let s = strs[0][i];
        // 遍历其他所有字符串
        for (let j = 1, jl = strs.length; j < jl; j++) {
            // 如果长度超过第一个字符串或匹配失败 匹配结束
            if (i === strs[j].length || s !== strs[j][i]) {
                return strs[0].substring(0, i)
            }
        }
    }
    return strs[0];
};