提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  Java

当前栏目

最长公共前缀（力扣 14）Java打败100%提交记录

JAVA
2023-03-14 22:54:31 时间

一、题目描述


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

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


示例 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%的提交。

相关文章