LeetCode题解：最长公共前缀

题目描述

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

示例

输出：strs = ["flower","flow","flight"]
输出："fl"

实现方法

思路

方法一：分治法

class Solution ，如果{
    public String longestCommonPrefix(String[] strs) {
        if(strs==null||strs.length == 0){
            return "";
        }else{
            return longestCommonPrefix(strs,0,strs.length-1);
        }
    }
    public String longestCommonPrefix(String[] strs,int start,int end){
        if(start==end){
            return strs[start];
        }else{
            int mid = (end - start)/2 + start;
            String lcpLeft = longestCommonPrefix(strs,start,mid);
            String lcpRight = longestCommonPrefix(strs,mid+1,end);
            return commonPrefix(lcpLeft,lcpRight);
        }
    }
    public String commonPrefix(String lcpLeft,String lcpRight){
        int minLength = Math.min(lcpLeft.length(),lcpRight.length());
        for(int i=0;i<minLength;i++){
            if(lcpLeft.charAt(i)!=lcpRight.charAt(i)){
                return lcpLeft.substring(0,i);
            }
        }
        return lcpLeft.substring(0,minLength);
    }
}

• 时间复杂度：O(mn)。
• 空间复杂度：O(mlogn)，其中 mm 是字符串数组中的字符串的平均长度，n是字符串的数量。空间复杂度主要取决于递归调用的层数，层数最大为 nlogn，每层需要 mm 的空间存储返回结果。

方法二：二分查找法

思路

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if(strs==null||strs.length == 0){
            return "";
        }
        int minLength = Integer.MAX_VALUE;
        for(String str:strs){
            minLength = Math.min(minLength,str.length());
        }
        int low=0,high=minLength;
        int mid = 0;
        while(low<high){
            mid = (high-low+1)/2 + low;
            if(isCommonPrefix(strs,mid)){
                low = mid;
            }else{
                high = mid-1;
            }
        }
        return strs[0].substring(0,low);
    }
    public boolean isCommonPrefix(String[] strs,int length){
        String baseStr = strs[0].substring(0,length);
        int count = strs.length;
        for(int i=1;i<count;i++){
            String str = strs[i];
            for(int j=0;j<length;j++){
                if(baseStr.charAt(j) != str.charAt(j)){
                    return false;
                }
            }
        }
        return true;
    }
}

• 时间复杂度：O(mn)。
• 空间复杂度：O(mlogn)，其中m是字符串数组中的字符串的平均长度，n是字符串的数量。空间复杂度主要取决于递归调用的层数，层数最大为logn，每层需要m的空间存储返回结果。

暴力法

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if(strs==null||strs.length == 0){
            return "";
        }
        int count = strs.length;
        String prefix = strs[0];
        for(int i = 0;i<count;i++){
            prefix = longestCommonPrefix(prefix,strs[i]);
            if(prefix.length()==0){
                break;
            }
        } 
        return prefix;
    }
    public String longestCommonPrefix(String str1,String str2){
        int length = Math.min(str1.length(),str2.length());
        int index = 0;
       while(index<length&&str1.charAt(index)==str2.charAt(index)){
           index++;
       }
       return str1.substring(0,index);
    }
}

• 时间复杂度：O(mn)，其中 m 是字符串数组中的字符串的平均长度，n 是字符串的数量。最坏情况下，字符串数组中的每个字符串的每个字符都会被比较一次。
• 空间复杂度：O(1)。