14. 最长公共前缀

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

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

示例 1：

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

示例 2：

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

提示：

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

横向扫描-startsWith API

因为公共前缀一定小于任意一个字符串，所以不妨初始化公共前缀为第一个字符串。遍历每个字符串，只要当前字符串不以 s 作为前缀，就将s缩短一个字符。

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

        // 初始化公共前缀为第一个字符串
        String s = strs[0];

        // 遍历数组中的每一个字符串
        for (String string : strs) {
            // 当当前字符串不以 s 作为前缀时，缩短 s
            while (!string.startsWith(s)) {
                // 将公共前缀 s 缩短一个字符，继续检查
                s = s.substring(0, s.length() - 1);
            }
        }

        // 返回最长公共前缀
        return s;
    }
}

• 时间复杂度：$O(n \times m)$，其中 $n$ 是字符串数组的长度，$m$ 是字符串的最大长度。
• 空间复杂度：$O(1)$，没有使用与输入大小相关的额外空间。

纵向扫描

两层for循环，第一层for循环遍历第一个字符串的索引，确定索引后，第二个for循环遍历剩下的字符串， 检查它们的该索引处的字符是否等于第一个字符串的该索引处的字符，如果不相等，直接返回第一个字符串的从0到该索引组成的子串。

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) {
                    // 返回第一个字符串的子串，即公共前缀
                    return strs[0].substring(0, i);
                }
            }
        }

        // 如果第一个字符串全部字符都匹配，返回第一个字符串
        return strs[0];
    }
}

• 时间复杂度： $O(mn)$，其中 $m$ 是字符串数组中的字符串的平均长度，$n$ 是字符串的数量。最坏情况下，字符串数组中的每个字符串的每个字符都会被比较一次。
• 空间复杂度： $O(1)$。使用的额外空间复杂度为常数。