力扣14. 最长公共前缀：Java四种解法详解

力扣14. 最长公共前缀：Java四种解法详解

题目描述

编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 ""。
示例：
输入：strs = ["flower","flow","flight"] → 输出："fl"
输入：strs = ["dog","racecar","car"] → 输出：""

解法一：横向扫描（逐步缩小前缀）

代码实现

public class Solution {
    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;
            while (j < prefix.length() && j < strs[i].length() && prefix.charAt(j) == strs[i].charAt(j)) {
                j++;
            }
            prefix = prefix.substring(0, j);
            if (prefix.isEmpty()) break;
        }
        return prefix;
    }
}

复杂度分析

• 时间复杂度：O(mn)，其中 m 是字符串平均长度，n 是数组长度。最坏情况下每个字符串都需完全比较。
• 空间复杂度：O(1)，仅需常数空间存储中间变量。

核心思路

以第一个字符串为初始前缀，依次与其他字符串逐字符比较，逐步缩小前缀范围。若中途前缀为空，则提前终止。

解法二：纵向扫描（逐列比较）

代码实现

public class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) return "";
        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() || strs[j].charAt(i) != c) {
                    return strs[0].substring(0, i);
                }
            }
        }
        return strs[0];
    }
}

复杂度分析

• 时间复杂度：O(mn)，逐列比较所有字符串的每个字符。
• 空间复杂度：O(1)，无需额外存储。

核心思路

从第一个字符开始，依次比较所有字符串的同一列字符，直到某一列不匹配，返回当前列之前的子串。

解法三：排序后首尾比较

代码实现

import java.util.Arrays;

public class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) return "";
        Arrays.sort(strs);
        String first = strs[0], last = strs[strs.length - 1];
        int minLen = Math.min(first.length(), last.length());
        int i = 0;
        while (i < minLen && first.charAt(i) == last.charAt(i)) {
            i++;
        }
        return first.substring(0, i);
    }
}

复杂度分析

• 时间复杂度：O(n log n + m)，排序耗时 O(n log n)，比较首尾字符串耗时 O(m)。
• 空间复杂度：O(log n)，排序的栈空间开销。

核心思路

排序后，最长公共前缀只需比较首尾字符串的公共部分。排序后首尾差异最大，因此公共前缀即全局公共前缀。

解法四：利用 startsWith 方法优化

代码实现

public class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) return "";
        String prefix = strs[0];
        for (String s : strs) {
            while (!s.startsWith(prefix)) {
                prefix = prefix.substring(0, prefix.length() - 1);
                if (prefix.isEmpty()) return "";
            }
        }
        return prefix;
    }
}

复杂度分析

• 时间复杂度：O(mn)，最坏情况下每个字符均需截取。
• 空间复杂度：O(1)，直接操作字符串。

核心思路

以第一个字符串为基准，逐步缩短前缀长度，直到所有字符串均以该前缀开头。利用 startsWith 简化字符比较逻辑。

各解法对比

示例解析

以输入 ["flower", "flow", "flight"] 为例：

1. 横向扫描：
   • 初始前缀 "flower"，与 "flow" 比较后缩小为 "flow"。
   • 再与 "flight" 比较，最终得到 "fl"。
2. 纵向扫描：
   • 比较所有字符串的第0列字符 f，第1列字符 l，第2列字符 o 与 i 不匹配，返回前两列 "fl"。

总结

以上四种方法均可高效解决问题，推荐根据场景选择：

• 纵向扫描：适用于字符串长度差异较小的场景，直接逐列比较效率高。
• 排序法：若字符串数量较少，排序后首尾比较更高效。
• startsWith：适合快速实现，代码简洁但需注意性能。

可直接复制代码到力扣运行，保证通过！

欢迎在评论区留言讨论其他优化思路或问题！