字符串简单3 种解法

#14最长公共前缀

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

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

原题

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

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

示例 1：

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

示例 2：

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

提示：

1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] 如果非空，则仅由小写英文字母组成

查看原题

解题主线

公共前缀长度不可能超过最短字符串；任一字符串在某列结束或字符不同即可立即返回。
横向合并维护当前公共前缀，前缀一旦为空即可短路。

解法 1：纵向扫描

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

时间复杂度： O(S)，S 为所有字符串字符总数
空间复杂度： O(1)，不计返回字符串

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 为最长公共前缀长度，来自中间字符串

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)，递归栈及活跃中间前缀

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