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-java / problems / _014_LongestCommonPrefix /
  https://github.com/masikkk/algorithms/tree/master/leetcode/leetcode/_014_LongestCommonPrefix

---