[Java] LeetCode 14. Longest Comm

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 "".

寻找字符串数组的最长公共前缀

Solution

法1：Horizontal scanning

1. 寻找规则：先找到前两个字符串的 longest common prefix，作为当前的prefix,再找到此 prefix 和 第三个字符串的 longest common prefix，以此遍历数组;
2. 初始prefix设为strs[0];
3. 用indexOf(prefix)判断当前字符串是否包含先前的公共前缀
   （1）若包含，则prefix不变，此字符串判断完毕
   （2）否则，prefix = prefix.substring(0,prefix.length()-1)

class Solution {
    //水平搜索，每两个字符串比较，时间复杂度 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.寻找规则：用strs[0]中的每个字符一个个和后面的字符串对比，从左到右，比较各字符串相同位置的字符是否相等；
2.返回条件：当前字符不等或此字符串已被扫描完毕

class Solution {
    //纵向对比，用strs[0]中的每个字符一个个和后面的字符串对比,时间复杂度 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

寻找规则：递归，左右半段分别寻找 longest common prefix，再合并

class Solution {
    //分治  ( Overloading : 同一个类中，方法名字相同，而参数不同。返回类型可以相同也可以不同。)
    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];  //规模最小，直接求解
        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){ //求两个字符串的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);
    }
}

解法参考:官方题解