LeetCode 14. 最长公共前缀

题目链接：LeetCode 14.最长公共前缀

题目描述

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

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

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

示例2：

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

解法一：常规思路

容易想到，整个字符串数组元素的最长公共前缀一定小于等于任意两个数组元素的最长公共前缀，所以可以先求出strs[0]和strs[1]的最长公共前缀ans，然后从index=2开始遍历到strs,length-1,。遍历过程中求strs[index]与ans的最长公共前缀，然后更新ans。当遍历完数组后得到的ans就是整个数组元素的最长公共前缀。

解法二:递归

求解整个数组元素的最长公共前缀，可以分解为求解strs[0]和strs[1:strs.length]的最长公共前缀，而后者又可以继续递归求解。所以定义一个递归函数pre，参数包括字符串数组和int 类型的start，作用是求解数组从start开始到数组长度(左闭右开)的最长公共前缀。递归基是数组start=strs.length-2的时候，因为此时就还剩下2个元素：strs[start]和strs[strs.length-1]，直接求解这两个字符串的最长公共前缀后返回即可。

代码如下：

public class Solution {
    /*求解任意两个字符串的最长公共前缀*/
    public String getPrefix(String a,String b){
        if(a.isEmpty()||b.isEmpty())
            return "";
        int i=0;
        String ans="";
        while(i<a.length()&&i<b.length()){
            if(a.charAt(i)==b.charAt(i)){
                ans+=a.charAt(i);
            }
            else
                break;
            ++i;
        }
        return ans;
    }
    /*递归求解*/
    public String pre(String[]strs,int start){
        if(strs.length<2)
            return strs[0];
        if(start==strs.length-2)
            return getPrefix(strs[start],strs[strs.length-1]);
        return getPrefix(strs[start],pre(strs,start+1));
    }
    /*线性遍历求解*/
    public String getAns(String[]strs){
        if(strs.length<2)
            return strs[0];
        String ans=getPrefix(strs[0],strs[1]);
        for(int i=2;i<strs.length;++i){
            ans=getPrefix(ans,strs[i]);
        }
        return ans;
    }
    public String longestCommonPrefix(String[] strs) {
//        String ans=pre(strs,0); //这是递归的方式
        String ans=getAns(strs);//这是线性遍历的方式
        return ans;
    }

}