力扣经典150题第二十题：最长公共前缀

力扣经典150题第二十题：最长公共前缀

1. 题目描述

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

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

示例 1：

输入：strs = [“flower”,“flow”,“flight”]

输出：“fl”

示例 2：

输入：strs = [“dog”,“racecar”,“car”]

输出：“”

解释：输入不存在公共前缀。

提示：

1 <= strs.length <= 200

0 <= strs[i].length <= 200

strs[i] 仅由小写英文字母组成

2. 解题思路

可以通过水平扫描的方法来解决。从第一个字符串开始，依次比较每个字符串相同位置的字符，直到遇到不同的字符为止。

3. 解题步骤

1. 如果字符串数组为空，直接返回空字符串。
2. 遍历第一个字符串的每个字符，依次与其他字符串的相同位置字符进行比较。
3. 如果遇到不同的字符，立即返回当前已经匹配的部分作为最长公共前缀。
4. 如果所有字符串都匹配到最短字符串的长度，说明这个最短字符串就是最长公共前缀。

4. 代码实现

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];
    }
}

5. 时间复杂度分析

• 设字符串数组中平均字符串长度为 m，共有 n 个字符串。
• 最坏情况下，需要比较的字符数为 m * n。
• 时间复杂度为 O(m * n)，其中 m 是字符串平均长度，n 是字符串个数。

6. 应用和扩展

• 该算法可以用于查找字符串数组中的最长公共前缀，通过水平扫描的方法逐个字符比较。
• 可以应用于处理字符串相关的问题，特别是字符串匹配和前缀处理的场景。

7. 总结

本文介绍了如何通过水平扫描的方法找出字符串数组中的最长公共前缀，通过逐个字符比较的方式来确定公共前缀的长度。

8. 参考资料

• LeetCode 官网