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

LeetCode.014.Longest Common Prefix 最长公共前缀

题目描述

014 Longest Common Prefix
https://leetcode.com/problems/longest-common-prefix/description/
https://leetcode-cn.com/problems/longest-common-prefix/

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 “”.

Example 1:

Input: ["flower","flow","flight"]
Output: "fl"

Example 2:

Input: ["dog","racecar","car"]
Output: ""

Explanation: There is no common prefix among the input strings.

Note:
All given inputs are in lowercase letters a-z.


解题过程

求字符串集合的最长公共前缀,自己只想到了穷举法。
看到提示里有 “All given inputs are in lowercase letters a-z” ,以为能用数组下表索引,但想来想去都得O(m*n)

垂直扫描法

动手写了一版,通过后看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 两个有序数组的中位数

阅读
评论
512
阅读预计2分钟
创建日期 2018-02-08
修改日期 2019-11-27
类别

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论