# 题目内容

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

# 解法一,暴力破解

老实说,对于这个暴力法一开始还想了一会,没想出来的是纠结于如何比较两个字符串中每一个字符。后面才想起,字符串也是有length的,也可以通过下标来获取其中的每一个字符。

var longestCommonPrefix = function(strs) {
    var re = '';
    if (!strs.length) return re;
    for (var j=0;j<strs[0].length;j++){//第j位
        for (var i=1;i<strs.length;i++){//第i个
            if (strs[i][j]!=strs[0][j]) return re
        }
        re += strs[0][j];
    }
    return re;
}
1
2
3
4
5
6
7
8
9
10
11

暴力破解法的思路就是,将下标为1及其后面的字符串的每一个字符和下标为0的字符想比较,如果此次循环的比较都相等,那公共前缀就加上此次比较的字符。这样讲很抽象,下面以一个数字为例。 ["flower","flow","flight"]

  • 外层循环第一次

    • 内存循环第一次 比较flow 和 flower,相等则继续循环

    • 内层循环第二次 比较flight 和 flower, 相等则完成第一次外层循环的所有内层循环

      re 为 f

  • 外层循环第二次

    • 内存循环第一次 比较flow 和 flower,相等则继续循环

    • 内层循环第二次 比较flight 和 flower, 相等则完成第一次外层循环的所有内层循环

      re 为fl

  • 外层循环第三次

    • 内存循环第一次 比较flow 和 flower,相等则继续循环
    • 内层循环第二次 比较flight 和 flower, 不相等则退出所有循环,答案为前一次的re

# 解法二,while配合slice

这个解法是在题解区名为JavaScript超快思路作者写的,测试后其时间复杂度确实不高。名副其实。

var longestCommonPrefix = function(strs) {
    let t = strs[0] || '';
    let i = 1;
    while(t && i < strs.length) {
        if(strs[i].indexOf(t) != 0) {
            t = t.slice(0, t.length - 1);
        } else {
            i++;
        }
    }
    return t;
}
1
2
3
4
5
6
7
8
9
10
11
12

这个解法的逻辑是,假定数组中的第一个字符串为最终答案。然后进入while循环,判断第二个字符串中是否包含第一个字符串,在上面的举例中,flow显然没有包含flower。此时就要削第一个字符串,削到第二个字符串包含他为止。后面如法炮制。

这个思路很赞的一点是把题目要求取最长公共前缀想的很透彻,既然是公共前缀就一定能满足包含于其它字符串的条件。又因为是前缀,所以当不满足条件是就从后往前削。

此外,此处假定数组第一项为答案,只是为了方便循环。假定第二项也没有问题,因为都会被削至满足条件。

一笔写于: 5/24/2020, 4:34:20 PM
扫码添加我的微信
个人
个人号
公众号
公众号