最长公共前缀

 

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

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

示例 1:

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

示例 2:

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

/**
 * @Auther: liuhaidong
 * Data: 2020/3/13 0013、0:40
 * Description:
 * @version: 1.0
 */
public class Test {
    public static void main(String[] args) {
        String[] strs ={"flower","flow","flight"};
        System.out.println(longestCommonPrefix(strs));
    }
    public static String longestCommonPrefix(String[] strs) {
        if (strs.length == 0){
            return "";
        }
        String result = strs[0];
        for (int i = 0; i < strs.length; i++) {
            while (strs[i].indexOf(result) != 0){
                result = result.substring(0,result.length()-1);
                if(result.length() == 0){
                    return "";
                }
            }
        }
        return result;
    }
}

java中String.indexOf()用法

查找指定字符或字符串在字符串中第一次出现地方的索引，未找到的情况返回 -1.

例如

String.indexOf(String str)

String str1="012345";
String str2="23";
System.out.println( str1.indexOf(str2) );

输出结果：2。

重载方法有

String.indexOf(String str，int index)

从index的地方开始找，返回第一次出现的索引

String str1="012345012345";
String str2="23";
System.out.println( str1.indexOf(str2,5) );

 输出结果：8.

 

 

/**
 * @Auther: liuhaidong
 * Data: 2020/3/13 0013、0:40
 * Description:
 * @version: 1.0
 */
public class Test {
    public static void main(String[] args) {
        String[] strs ={"leetcode","leet","lee","le"};
        System.out.println(longestCommonPrefix(strs));
    }
    public static String longestCommonPrefix(String[] strs) {
        if (strs.length == 0){
            return "";
        }
        int length = strs.length;
        return helper(strs,0,strs.length-1);
    }

    private static String helper(String[] strs, int left, int right) {
        if(left == right){
            return strs[left];
        }else {
            int mid = (left + right)/2;
            String leftStr = helper(strs,left,mid);
            String rightStr = helper(strs,mid+1,right);
            return helpfix(leftStr,rightStr);
        }
    }

    private static String helpfix(String leftStr, String rightStr) {
        int minLength = Math.min(leftStr.length(),rightStr.length());
        for(int i =0;i<minLength;i++){
            if(leftStr.charAt(i) != rightStr.charAt(i)){
                return leftStr.substring(0,i);
            }
        }
        return leftStr.substring(0,minLength);
    }
}