字符串简单3 种解法

#14最长公共前缀

返回字符串数组中所有字符串共有的最长起始片段。

#字符串#纵向扫描#分治

解题主线

公共前缀长度不可能超过最短字符串；任一字符串在某列结束或字符不同即可立即返回。

横向合并维护当前公共前缀，前缀一旦为空即可短路。

解法 1：纵向扫描

逐列比较首字符串的字符与其余字符串同位置字符。

时间复杂度

O(S)，S 为所有字符串字符总数

空间复杂度

O(1)，不计返回字符串

14. 最长公共前缀 · 纵向扫描

java

final class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) return "";
        for (int i = 0; i < strs[0].length(); i++) {
            char expected = strs[0].charAt(i);
            for (int j = 1; j < strs.length; j++) {
                if (i == strs[j].length() || strs[j].charAt(i) != expected) {
                    return strs[0].substring(0, i);
                }
            }
        }
        return strs[0];
    }
}

逐列比较首字符串的字符与其余字符串同位置字符。

解法 2：横向合并

依次求当前前缀与下一个字符串的两串公共前缀。

时间复杂度

O(S)

空间复杂度

O(m)，m 为最长公共前缀长度，来自中间字符串

14. 最长公共前缀 · 横向合并

java

final 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 && !prefix.isEmpty(); i++) {
            prefix = commonPrefix(prefix, strs[i]);
        }
        return prefix;
    }

    private String commonPrefix(String first, String second) {
        int length = Math.min(first.length(), second.length());
        int i = 0;
        while (i < length && first.charAt(i) == second.charAt(i)) i++;
        return first.substring(0, i);
    }
}

依次求当前前缀与下一个字符串的两串公共前缀。

解法 3：分治合并

递归求左右字符串区间的公共前缀，再合并两个结果。

时间复杂度

O(S)

空间复杂度

O(log n + m log n)，递归栈及活跃中间前缀

14. 最长公共前缀 · 分治合并

java

final class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) return "";
        return divide(strs, 0, strs.length - 1);
    }

    private String divide(String[] strs, int left, int right) {
        if (left == right) return strs[left];
        int middle = left + (right - left) / 2;
        return commonPrefix(divide(strs, left, middle), divide(strs, middle + 1, right));
    }

    private String commonPrefix(String first, String second) {
        int length = Math.min(first.length(), second.length());
        int i = 0;
        while (i < length && first.charAt(i) == second.charAt(i)) i++;
        return first.substring(0, i);
    }
}

递归求左右字符串区间的公共前缀，再合并两个结果。

边界与易错点

空数组应返回空串。
纵向扫描必须先判断 i 是否到达当前字符串长度，再调用 charAt。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

easy/Q014_longestCommonPrefix.java