14.最长公共前缀

题目:14.最长公共前缀

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

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

• 示例 1：

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

• 示例 2：

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

• 提示：

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

思路

可以使用纵向扫描的方法，从第一个字符开始比较每个字符串的相应位置的字符，直到遇到不同字符或到达某个字符串的末尾。

1. 初始检查：

   • 如果输入数组为空或第一个字符串长度为零，直接返回空字符串。

2. 纵向扫描：

   • 获取第一个字符串的长度。
   • 依次检查第一个字符串的每一个字符，逐个字符和其他字符串相应位置的字符进行比较。
   • 如果发现字符不同或者到达了某个字符串的末尾，返回当前已经匹配的最长公共前缀。

3. 返回结果：

   • 如果第一个字符串的所有字符都匹配，返回整个字符串作为公共前缀。

• 时间复杂度:O(mn)
• 空间复杂度:O(1)

代码

public String longestCommonPrefix(String[] strs) {
    if (strs == null || strs[0].isEmpty()) {
        return "";
    }
    // 取第一个字符串的长度
    int length = strs[0].length();
    // 依次检查每一个字符
    for (int i = 0; i < length; i++) {
        // 取第一个字符串的第i个字符
        char c = strs[0].charAt(i);
        // 如果到达了某个字符串的末尾，或者字符不同
        for (int j = 0; j < strs.length; j++) {
            if (i >= strs[j].length() || strs[j].charAt(i) != c) {
                // 返回当前公共前缀
                return strs[0].substring(0, i);
            }
        }
    }
    // 如果第一个字符串的所有字符都匹配，返回整个字符串
    return strs[0];
}