Description

Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string "".

尋找字符串?dāng)?shù)組的最長公共前綴

Solution

法1：Horizontal scanning

1. 尋找規(guī)則：先找到前兩個(gè)字符串的 longest common prefix，作為當(dāng)前的prefix,再找到此 prefix 和 第三個(gè)字符串的 longest common prefix，以此遍歷數(shù)組;
2. 初始prefix設(shè)為strs[0];
3. 用indexOf(prefix)判斷當(dāng)前字符串是否包含先前的公共前綴
   （1）若包含，則prefix不變，此字符串判斷完畢
   （2）否則，prefix = prefix.substring(0,prefix.length()-1)

class Solution {
    //水平搜索，每兩個(gè)字符串比較，時(shí)間復(fù)雜度 O(S)
    public String longestCommonPrefix(String[] strs) {
        if(strs.length == 0) return "";
        String prefix = strs[0];
        for(int i = 1;i<strs.length;i++)
            while(strs[i].indexOf(prefix)!=0){  //若 == 0，說明strs[i] 從開頭包含prefix,則prefix就是公共前綴
                prefix = prefix.substring(0,prefix.length()-1);
                if(prefix == "") return "";
            }
        return prefix;
    }
}

法2：Vertical scanning

1.尋找規(guī)則：用strs[0]中的每個(gè)字符一個(gè)個(gè)和后面的字符串對比，從左到右，比較各字符串相同位置的字符是否相等；
2.返回條件：當(dāng)前字符不等或此字符串已被掃描完畢

class Solution {
    //縱向?qū)Ρ龋胹trs[0]中的每個(gè)字符一個(gè)個(gè)和后面的字符串對比,時(shí)間復(fù)雜度 O(S)
    public String longestCommonPrefix(String[] strs) {
        if(strs.length == 0) return "";
        for(int i = 0;i<strs[0].length();i++){
            char c = strs[0].charAt(i);
            for(int j = 1;j<strs.length;j++){
                if(i ==strs[j].length() || strs[j].charAt(i)!=c)
                    return strs[0].substring(0,i);
            }
        }
        return strs[0];
    }
}

法3：Divide and conquer

尋找規(guī)則：遞歸，左右半段分別尋找 longest common prefix，再合并

class Solution {
    //分治  ( Overloading : 同一個(gè)類中，方法名字相同，而參數(shù)不同。返回類型可以相同也可以不同。)
    public String longestCommonPrefix(String[] strs) {
        if(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];  //規(guī)模最小，直接求解
        else{
            int mid = (l + r)/2;
            String lcpLeft = longestCommonPrefix(strs,l,mid);
            String lcpRight = longestCommonPrefix(strs,mid+1,r);
            return commonPrefix(lcpLeft,lcpRight);
        }
    }
    
    private String commonPrefix(String left,String right){ //求兩個(gè)字符串的LCP
        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);
    }
}

解法參考:官方題解