一、题目描述

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

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

示例 1：

输入：strs = [“flower”,”flow”,”flight”]
输出：”fl”

示例 2：

输入：strs = [“dog”,”racecar”,”car”]
输出：””
解释：输入不存在公共前缀。

提示：

1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] 仅由小写英文字母组成

二、思路讲解

逐位更新公共前缀。将所有字符串的第i位（从0开始）与第一个字符串的第i位比较。如果第i位都相同，说明是相同前缀，将它追加到要返回的字符串s（初始为空串）上；如果有不相同，直接返回 s；

三、Java代码实现

class Solution {
    public String longestCommonPrefix(String[] strs) {

        String s = "";
        int len = strs[0].length();
        for(int i=0; i<strs.length; i++){
            if(len > strs[i].length()){
                len = strs[i].length();
            }
        }

        for(int i=0; i<len; i++){
            char temp = strs[0].charAt(i);
            for(int j=1; j<strs.length; j++){
                if(temp != strs[j].charAt(i)){
                    return s;
                }
            }
            s += temp;
        }
        return s;
    }
}

四、时空复杂度分析

时间复杂度： O(MN) M是数组中字符串平均长度，N是数组长度。最坏情况需要遍历数组中所有字符串

空间复杂度： O(1)

五、代码优化

直接将s初始化为最短的字符串，然后逐一判断数组中所有的字符串是否以s开头。若不，那么将s更新为二者的共同前缀。

class Solution {
    public String longestCommonPrefix(String[] strs) {
        String s = strs[0];
        //令s为最短的字符串
        for(int i=0; i<strs.length; i++){
            if(strs[i].length() < s.length()){
                s = strs[i];
            }
        }

        for(int i=0; i<strs.length; i++){
            //判断第i个字符串的前缀是不是s，如果不是，取共同前缀
            if(!strs[i].startsWith(s)){ 
                s = sub(strs[i], s);
            }
        }
        return s;
    }

    //取两个字符串的共同前缀
    public static String sub(String a, String b){
        int len = Math.min(a.length(), b.length());
        int i;
        for(i=0; i<len; i++){
            if(a.charAt(i) != b.charAt(i)){
                break;
            }
        }
        return a.substring(0, i);
    }
}

极大减少了运行时间，前面的方法在力扣中需要8ms，打败8%的提交

这个方法只需0ms，打败100%的提交。

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/125048.html