题目内容

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

解法一，暴力破解

老实说，对于这个暴力法一开始还想了一会，没想出来的是纠结于如何比较两个字符串中每一个字符。后面才想起，字符串也是有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及其后面的字符串的每一个字符和下标为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;
}

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

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

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