小学生都能看懂的题解 | #最长公共前缀#

问题描述

我们有一个字符串数组，比如 ["abca", "abc", "abca", "abc", "abcc"]。任务是找到这些字符串开头相同的部分（也叫“最长公共前缀”）。就像找兄弟姐妹名字开头一样：如果大家都叫"李小明"、"李小红"、"李小刚"，那最长公共前缀就是"李小"。

例如：

• ["abca", "abc", "abca", "abc", "abcc"] 的最长公共前缀是 "abc"。
• ["apple", "app", "apricot"] 的最长公共前缀是 "ap"。

思路

我们可以通过以下方法找到最长公共前缀：

1. 拿第一个字符串当做“候选前缀”，假设它就是最长的前缀。
2. 和其他的字符串进行比较，看每个字符串是不是以这个“候选前缀”开头。
3. 如果不匹配，就缩短这个前缀，把它的最后一个字母去掉，直到它变成大家都开头相同的部分。
4. 最后得到的“候选前缀”就是最长公共前缀。

代码实现

下面是用 Java 编写的代码，已经按步骤写好了：

public class Solution {
    public static String longestCommonPrefix(String[] strs) {
        // 如果数组为空，返回空字符串
        if (strs == null || strs.length == 0) {
            return "";
        }

        // 设第一个字符串是最长公共前缀的候选
        String prefix = strs[0];

        // 从第二个字符串开始，一个一个检查
        for (int i = 1; i < strs.length; i++) {
            // 如果当前前缀不是 strs[i] 的开头，就把前缀缩短
            while (strs[i].indexOf(prefix) != 0) {
                // 去掉前缀的最后一个字母
                prefix = prefix.substring(0, prefix.length() - 1);
                // 如果前缀变成空，就返回空
                if (prefix.isEmpty()) {
                    return "";
                }
            }
        }

        // 返回最后得到的前缀
        return prefix;
    }

    public static void main(String[] args) {
        // 测试用例
        String[] strs1 = {"abca", "abc", "abca", "abc", "abcc"};
        System.out.println(longestCommonPrefix(strs1)); // 输出: "abc"

        String[] strs2 = {"abc"};
        System.out.println(longestCommonPrefix(strs2)); // 输出: "abc"
    }
}

代码解释

1. 初始化：检查数组是否为空，如果是空的，就返回空字符串。
2. 设定候选前缀：把第一个字符串当做“候选前缀”。
3. 检查和缩短前缀：从第二个字符串开始，每个字符串都和“候选前缀”比：
   • 如果某个字符串不是以“候选前缀”开头，就把“候选前缀”最后一个字母去掉，再试试。
   • 不断重复，直到找到一个它们都开头相同的部分。
4. 返回结果：最后得到的“候选前缀”就是我们想要的最长公共前缀。

示例

1. 示例1：如果输入 ["abca", "abc", "abca", "abc", "abcc"]

   • 首先拿 abca 作为候选前缀。
   • 第二个字符串是 abc，和 abca 不完全相同，所以候选前缀缩短成 abc。
   • 之后所有字符串都以 abc 开头，所以最后的最长公共前缀就是 abc。

2. 示例2：如果输入 ["apple", "app", "apricot"]

   • 拿 apple 作为候选前缀，和 app 不完全相同，缩短成 app。
   • 再比较 app 和 apricot，结果它们前面都有 ap。
   • 所以最长公共前缀是 ap。

希望这篇文章对你有帮助👍。