LeetCode刷题-14.最长公共前缀

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-common-prefix/

一、题目

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

示例 1：

输入：strs = ["flower","flow","flight"]
输出："fl"

示例 2：

输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。

提示：

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i] 仅由小写英文字母组成

二、题解

解题源码: 链接

2.1.横向扫描

2.1.1.算法步骤

• 当字符串数组长度为 0 时则公共前缀为空，直接返回
• 令最长公共前缀 prefix 的值为第一个字符串，进行初始化
• 遍历后面的字符串，依次将其与 prefix 进行比较，两两找出公共前缀，最终结果即为最长公共前缀
• 如果查找过程中出现了 prefix 为空的情况，则公共前缀不存在直接返回

2.1.2.动画演示

2.1.3.复杂度分析

• 时间复杂度：O(mn)，其中 m 是字符串数组中的字符串的平均长度，n 是字符串的数量。最坏情况下，字符串数组中的每个字符串的每个字符都会被比较一次。
• 空间复杂度：O(1)。使用的额外空间复杂度为常数。

2.1.4.参考代码

解题源码: 链接

public class Id_0014_CrosswiseScan implements Id_0014 {

    @Override
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }

        String prefix = strs[0];

        for (int i = 1; i < strs.length; i++) {
            int j = 0;
            String str = strs[i];
            int le = Math.min(str.length(),prefix.length());
            while (j < le && prefix.charAt(j) == str.charAt(j)) {
                j++;
            }
            prefix = str.substring(0, j);
            //判断是否一个都对不上
            if (j == 0) {
                break;
            }
        }

        return prefix;
    }

}

2.2.纵向扫描

2.2.1.算法步骤

• 当字符串数组长度为 0 时则公共前缀为空，直接返回
• 从前往后遍历所有字符串的每一列，比较相同列上的字符是否相同，如果相同则继续对下一列进行比较，如果不相同则当前列不再属于公共前缀，当前列之前的部分为最长公共前缀

2.2.2.动画演示

2.2.3.复杂度分析

• 时间复杂度：O(mn)，其中 m 是字符串数组中的字符串的平均长度，n 是字符串的数量。最坏情况下，字符串数组中的每个字符串的每个字符都会被比较一次。
• 空间复杂度：O(1)。使用的额外空间复杂度为常数。

2.2.4.参考代码

解题源码: 链接

public class Id_0014_LongitudinalScan implements Id_0014{

    @Override
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }

        int length = strs[0].length();
        int count = strs.length;
        for (int i = 0; i < length; i++) {
            char c = strs[0].charAt(i);
            for (int j = 1; j < count; j++) {
                if (i == strs[j].length() || strs[j].charAt(i) != c) {
                    return strs[0].substring(0, i);
                }
            }
        }
        return strs[0];
    }

}

2.3.分治

2.2.1.算法步骤

• 将字符串数组，分为左右两个子数组，先求左字符串数组的前缀，再求右字符串数组的前缀，再求两个前缀的前缀。
• 许多字符串的前缀不好求，两个字符串的前缀肯定好求。

2.2.2.动画演示

2.2.4.参考代码

解题源码: 链接

public class Id_0014_DivideAndConquer implements Id_0014 {

    @Override
    public String longestCommonPrefix(String[] strs) {
        return getPrefix(strs, 0, strs.length - 1);
    }

    private String getPrefix(String[] strs, int low, int high) {
        // 子数组只有一个字符串，那它本身就是最长前缀
        if (low == high) {
            return strs[low];
        }
        // 分为两个子数组
        int mid = low + (high - low) / 2;
        // 求左数组的最长前缀
        String leftPrefix = getPrefix(strs, low, mid);
        // 求右数组的最长前缀
        String rightPrefix = getPrefix(strs, mid + 1, high);
        // 求两个最长前缀的最长前缀
        int length = Math.min(leftPrefix.length(), rightPrefix.length());
        for (int i = 0; i < length; i++) {
            if (leftPrefix.charAt(i) != rightPrefix.charAt(i)) {
                return leftPrefix.substring(0, i);
            }
        }
        return leftPrefix.substring(0, length);
    }
    
}

参考：https://leetcode-cn.com/problems/longest-common-prefix/solution/zui-chang-gong-gong-qian-zhui-by-leetcode-solution/

以上是个人学习记录，如有不正确请多多包涵，也欢迎评论告诉我，谢谢~