最长公共前缀|博客系列

# 题目描述

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

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

示例一🌰:

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

@前端进阶之旅: 代码已经复制到剪贴板

示例二🌰:

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

@前端进阶之旅: 代码已经复制到剪贴板

说明:

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

# 解题思路

一组字符串中, 单个字符串有长也有短, 可以先将字符串组按长度排序, 然后假设最短的字符串为公共前缀, 依次与后面的字符串做比较, 直到找到公共前缀.

考虑输入的数组的长度为0, 1的情况;
将字符串组按长度排序;
设置公共前缀comStr为排序后的第一项(数组中的最短字符串);
设置当前遍历的下标i;
利用while循环, 循环条件为i < strs.length;
依次比较comStr和strs[i].substr(0, comStr.length)项;
若上面的比较不同, 则切去comStr的最后一项, 接着比较;
若上面的比较相同, 则将i加上一;
需要注意若是comStr为空字符串了则可以返回了.

# coding

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    if (!strs || strs.length <= 0) return '';
    if (strs.length === 1) return strs[0];
    strs = strs.sort(compare)
    function compare (a, b) { // 按照字符串的长度进行排序
        return a.length - b.length
    }
    let comStr = strs[0], // 假设第一项为最长前缀
        i = 1;
    while (i < strs.length) {
        if (comStr === '') return '';
        if (strs[i].substr(0, comStr.length) !== comStr) {
            comStr = comStr.substring(0, comStr.length - 1);
        } else {
            i++;
        }
    }
    return comStr;
};

@前端进阶之旅: 代码已经复制到剪贴板

执行用时68ms, 内存消耗33.6MB.

测试代码:

longestCommonPrefix(["flower","flow","flight"])
// "fl"

@前端进阶之旅: 代码已经复制到剪贴板

# 题目描述

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

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

示例一🌰:

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

@前端进阶之旅: 代码已经复制到剪贴板

示例二🌰:

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

@前端进阶之旅: 代码已经复制到剪贴板

说明:

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

# 解题思路

考虑输入的数组的长度为0, 1的情况;
将字符串组按长度排序;
设置公共前缀comStr为排序后的第一项(数组中的最短字符串);
设置当前遍历的下标i;
利用while循环, 循环条件为i < strs.length;
依次比较comStr和strs[i].substr(0, comStr.length)项;
若上面的比较不同, 则切去comStr的最后一项, 接着比较;
若上面的比较相同, 则将i加上一;
需要注意若是comStr为空字符串了则可以返回了.

# coding

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    if (!strs || strs.length <= 0) return '';
    if (strs.length === 1) return strs[0];
    strs = strs.sort(compare)
    function compare (a, b) { // 按照字符串的长度进行排序
        return a.length - b.length
    }
    let comStr = strs[0], // 假设第一项为最长前缀
        i = 1;
    while (i < strs.length) {
        if (comStr === '') return '';
        if (strs[i].substr(0, comStr.length) !== comStr) {
            comStr = comStr.substring(0, comStr.length - 1);
        } else {
            i++;
        }
    }
    return comStr;
};

@前端进阶之旅: 代码已经复制到剪贴板

执行用时68ms, 内存消耗33.6MB.

测试代码:

longestCommonPrefix(["flower","flow","flight"])
// "fl"

@前端进阶之旅: 代码已经复制到剪贴板