leetcode練習問題集——14.最大共通プレフィックス

テーマ
文字列配列の最長共通プレフィックスを検索する関数を作成します。
共通のプレフィックスが存在しない場合は、空の文字列「」を返します。
例1：入力：[[flower]，[flow]，[flight]出力：[flight]
例2：入力：「"dog"は、"racecar"は、"car"は出力されます。"説明：入力は共通プレフィックスが存在しません。
説明：すべての入力には小文字a-zのみが含まれます。
アルゴリズム1

public class P14Longest_Common_Prefix {
    public String longestCommonPrefix(String[] strs) {
        int sl = Integer.MAX_VALUE;
        int index = 0;
        String r = "";
        if(strs==null||strs.length==0){
            return "";
        }
        for(int i = 0;i<strs.length;i++){
            if(strs[i].equals("")){
                return "";
            }
            int curl = sl;
            sl = curl>strs[i].length()?strs[i].length():sl;
            index = curl>strs[i].length()?i:index;
        }
        loop:
        for(int j = 0;j<strs[index].length();j++){
            for(int k= 0;k<strs.length;k++){
                if(strs[k].charAt(j)==strs[index].charAt(j)){
                    if(k==strs.length-1){
                        r += strs[index].charAt(j);
                    }else {
                        continue;
                    }
                }else {
                    break loop;
                }
            }
        }
        return r;
    }
}

構想：暴力解法、直接文字列配列の中で最も短い文字列を探し出して、その他の列でこの列と一致します。
アルゴリズム2

public String longestCommonPrefix(String[] strs) {
    if (strs == null || strs.length == 0) return "";    
        return longestCommonPrefix(strs, 0 , strs.length - 1);
}

private String longestCommonPrefix(String[] strs, int l, int r) {
    if (l == r) {
        return strs[l];
    }
    else {
        int mid = (l + r)/2;
        String lcpLeft =   longestCommonPrefix(strs, l , mid);
        String lcpRight =  longestCommonPrefix(strs, mid + 1,r);
        return commonPrefix(lcpLeft, lcpRight);
   }
}

String commonPrefix(String left,String right) {
    int min = Math.min(left.length(), right.length());       
    for (int i = 0; i < min; i++) {
        if ( left.charAt(i) != right.charAt(i) )
            return left.substring(0, i);
    }
    return left.substring(0, min);
}

考え方：長い共通プレフィックスを解決する思想を分治し、コードを参照してください。分かりやすいです。