当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.014.Longest Common Prefix

LeetCode.014.Longest Common Prefix


题目描述

Write a function to find the longest common prefix string amongst an array of strings.


解题过程

求字符串集合的最长公共前缀,自己只想到了穷举法。

垂直扫描法

动手写了一版,通过后看Solution,这道题的Solution写的非常好,图文并茂,给出了好几种解法,看后才知道原来我的方法是垂直搜索法,搜索过程就是比较第一个字符串的第i个字符是否在所有字符串的位置i都出现,如果不出现就返回当前搜索到的最长前缀:

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if(strs.length==0)
            return "";
        String prefix = "";
        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())
                    return prefix;
                if(c!=strs[j].charAt(i))
                    return prefix;
            }
            prefix += c;//c在所有字符串中出现
        }
        return prefix;
    }
}

水平扫描法

还有一种方法是水平扫描:先找前两个字符串的最长公共前缀,假如是prefix,然后再找prefix和第3个字符串的最长公共前缀,直到遍历完所有字符串。
Solution中给出的代码非常简洁,值得一看:

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) {//找prefix和strs[i]的公共前缀
            prefix = prefix.substring(0, prefix.length() - 1);
            if (prefix.isEmpty()) return "";
        }        
    return prefix;
}

此外Solution中还介绍了分治法二分搜索法,想法很不错,但对于解决这个问题来说,复杂度没明显减少,但代码复杂了不少。


GitHub代码


上一篇 LeetCode.021.Merge Two Sorted Lists

下一篇 LeetCode.004.Median of Two Sorted Arrays

阅读
424
阅读预计2分钟
创建日期 2018-02-08
修改日期 2018-02-08
类别
百度推荐