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

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

题目描述

014 Longest Common Prefix
https://leetcode-cn.com/problems/longest-common-prefix/
https://leetcode.com/problems/longest-common-prefix/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 “”.

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)

2018垂直扫描

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

private static class SolutionV2018 {
    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;
    }
}

2019垂直扫描

时间复杂度 O(mn),空间复杂度 O(1)

private static class SolutionV2019 {
    public String longestCommonPrefix(String[] strs) {
        if (0 == strs.length) {
            return "";
        }
        int i = 0, j = 0;
        for (; i < strs[0].length(); i++) {
            for (j = 1; j < strs.length; j++) {
                if (i >= strs[j].length() || strs[0].charAt(i) != strs[j].charAt(i)) {
                    return strs[0].substring(0, i);
                }
            }
        }
        return strs[0].substring(0, i);
    }
}

2020垂直扫描

其实不需要 StringBuilder 来记录前缀,找到最大前缀长度后直接 substring 就行了。
时间复杂度 O(mn),空间复杂度 O(m)

private static class SolutionV202006 {
    public String longestCommonPrefix(String[] strs) {
        if (null == strs || strs.length < 1) {
            return "";
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < strs[0].length(); i++) {
            char ch = strs[0].charAt(i);
            for (int j = 1; j < strs.length; j++) {
                if (i >= strs[j].length() || ch != strs[j].charAt(i)) {
                    return sb.toString();
                }
            }
            sb.append(ch);
        }
        return sb.toString();
    }
}

水平扫描法

还有一种方法是水平扫描:先找前两个字符串的最长公共前缀,假如是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;
}

分治法

先求前一半字符串的最长公共前缀 leftLCP,再求后一半字符串的最长公共前缀 rightLCP,最后求 leftLCP 和 rightLCP 的最长公共前缀,递归实现。

二分搜索

先找到最短字符串的长度 minLength,则最长公共前缀的长度一定在 [0, minLength] 范围内,可以使用二分搜索进行查找,每次取子串 substring(0, mid) 并判断是否公共子串,是的话在 [mid, minLength] 中继续搜索,否则在 [0, mid] 中搜索。

前缀树/字典树


GitHub代码


上一篇 LeetCode.021.Merge Two Sorted Lists 合并两个有序链表

下一篇 LeetCode.004.Median of Two Sorted Arrays 两个有序数组的中位数

阅读
评论
820
阅读预计4分钟
创建日期 2018-02-08
修改日期 2020-06-15
类别

页面信息

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

评论