最长公共前缀 | LeetCode-14

这是一道一看就会，一做就错的题目！

---

LeetCode链接：14. 最长公共前缀 ---

1.题目描述

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

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

示例 1：

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

示例 2：

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

提示：

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

2.题解

2.1 横向扫描

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

        // 初始化结果为第一个字符串。我们将不断缩短这个字符串，直到找到所有字符串的公共前缀
        String result = strs[0];

        // 从第二个字符串开始遍历，和结果字符串进行比较
        for (int i = 1; i < strs.length; i++) {
            int j;
            // 逐字符比较 result 和当前字符串 strs[i]
            // 比较的条件是：两个字符串都没有越界，并且字符相等
            for (j = 0; j < result.length() && j < strs[i].length(); j++) {
                // 一旦找到不匹配的字符，停止比较
                if (result.charAt(j) != strs[i].charAt(j))
                    break;
            }
            // 更新 result 为当前匹配的最长前缀
            result = result.substring(0, j);

            // 如果 result 变成空字符串，意味着不存在公共前缀，直接返回空字符串
            if (result.equals(""))
                return result;
        }
        // 返回找到的最长公共前缀
        return result;
    }
}

• 图解：

2.2 纵向扫描

class Solution {
    public String longestCommonPrefix(String[] strs) {
        // 如果输入为空或字符串数组长度为0，直接返回空字符串
        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) {
                    // 返回第一个字符串的前缀，长度为i
                    return strs[0].substring(0, i);
                }
            }
        }

        // 如果循环结束，说明所有字符串的前缀一致，返回第一个字符串
        return strs[0];
    }
}

• 图解