题目

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

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

示例 1:

输入: ["flower","flow","flight"]
输出: "fl"
示例 2:

输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。

说明:

所有输入只包含小写字母 a-z 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-common-prefix
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法1：

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if(strs==null||strs.length==0) return "";
        return longest(strs,0,strs.length-1);
    }
    public String longest(String[] strs, int start, int end){
        if(start==end){
            return strs[start];
        }
        int mid=(end+start)/2;
        String leftstr=longest(strs,start,mid);
        String rightstr=longest(strs,mid+1,end);
        return judge(leftstr,rightstr);
    }
    public String judge(String leftstr,String rightstr){
        int n =  Math.min(leftstr.length(),rightstr.length());
        for(int i = 0 ; i < n; i++){
            while(leftstr.charAt(i)!=rightstr.charAt(i)){
                return leftstr.substring(0,i);
            }
        }
        return leftstr.substring(0,n);
    }
}