LeetCode——最长公共前缀

NO.14 最长公共前缀简单

思路一：依次LCP法假设输入数组为[“leetcode”,”leetcodes”,”leetgo”,”letsgo”]：1. 我们先让0号元素和1号元素求公共前缀 LCP(0号元素，1号元素)求出最长公共前缀prefix=”leetcode”。2. 然后prefix=LCP[prefix，2号元素]求出prefix=leet。3. prefix=LCP[prefix，3号元素]求出prefix=le。求出最终的答案”le”。

public String longestCommonPrefix(String[] strs) {
//        如果数组元素个数为0，返回""
        if (strs.length==0)return "";
//        假设最长公共前缀是数组第一个元素
        String prefix=strs[0];
//        从前向后数组元素依次和当前最长公共前缀比较
        for (int i=1;i<strs.length;i++){
            //如果当前被比较的元素不含有当前最长前缀，就将当前最长前缀从后面减少一位
            while (strs[i].indexOf(prefix)!=0){
                prefix=prefix.substring(0,prefix.length()-1);
//                如果当前最长前缀已经为空，则说明数组中的元素没有公共前缀，直接返回""
                if (prefix.isEmpty())return "";
            }
        }
        return prefix;
    }

时间复杂度:O(s) s是数组中每个字符串的字符个数之和

空间复杂度:O(1)

思路二：优化依次LCP法 上述方法中，无论数组每个元素的长短我们都需要从第一个数组元素比较到最后一个数组元素，所以有一个明显的问题：如果数组中最后一个元素非常短，但是我们仍然需要比较s次。

可以将思路一的算法改为从前往后枚举字符串的每一列，先比较每个字符串相同列上的字符（即不同字符串相同下标的字符）然后再进行对下一列的比较。

依然假设输入数组为[“leetcode”,”leetcodes”,”leetgo”,”letsgo”]：1. 第一次循环i=0先用0号元素的第一个字符”l”，去和1号元素的第一个字符比较，相等；继续去和第2号元素的第一个字符比较，相等；继续去和第3号元素的第一个字符比较，相等；2. 第二次循环i=1再用0号元素的第二个字符”e”，去和1号元素的第二个字符比较，相等；继续去和第2号元素的第二个字符比较，相等；继续去和第3号元素的第二个字符比较，相等；3. 第三次循环i=2再用0号元素的第三个字符”e”，去和1号元素的第三个字符比较，相等；继续去和第2号元素的第三个字符比较，相等；继续去和第3号元素的第三个字符比较，不相等，则返回数组0号元素[0,i)字符，即”le”。

public String longestCommonPrefix(String[] strs) {
        if (strs==null||strs.length==0)return "";
//        将数组的0号元素的每个字符逐一取出进行比较
        for (int i=0;i<strs[0].length();i++){
//            取出数组0号元素的i号字符
            char c = strs[0].charAt(i);
//            将c和数组的每个元素的i号字符进行比较
            for (int j=1;j<strs.length;j++){
//                如果某个元素的所有字符都已比较完毕（即最短的元素）或者某个元素的第i个字符和c不相等
                if (i==strs[j].length()||strs[j].charAt(i)!=c){
//                    则0号元素的[0，i)号字符就是公共前缀
                    return strs[0].substring(0,i);
                }
            }
        }
        return strs[0];
    }

时间复杂度:O(s) s是数组中每个字符串的字符个数之和。在最坏情况下，本算法的效率与算法一相同，但是最好的情况下，算法只需要进行 n*minLen 次比较，其中minLen是数组中最短字符串的长度。

空间复杂度:O(1)

思路三：分治法 其实这方法也是上述的依次LCP法的一种优化方法，LCP(s1,s2,…,sn)=LCP(LCP(s1,s2,…,smid),LCP(smid+1,smid+2,…sn))。

先将数组元素分成两部分，分别求LCP得到lcpLeft和lcpRight，最后求LCP(lcpLeft，lcpRight)得到prefix。

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);
}

时间复杂度：O(S)，S是所有字符串中字符数量的总和，S=m∗n。

空间复杂度：O(m*log(n))

本人菜鸟，有错误请告知，感激不尽！

更多题解和学习记录博客:博客、github

NO.14 最长公共前缀 简单

NO.14 最长公共前缀简单