14. 最长公共前缀

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

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

示例 1：

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

示例 2：

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

提示：

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i] 如果非空，则仅由小写英文字母组成

---

题解：

看示例 1：

flower

flow

flight

从左到右，竖着看，第一列全是 f，第二列全是 l，第三列就不全一样了，所以「最长公共前缀」是 fl。

具体算法如下：

从左到右遍历 strs 的每一列。

设当前遍历到第 j 列，从上到下遍历这一列的字母。

设当前遍历到第 i 行，即 strs[i][j]。如果 j 等于 strs[i] 的长度，或者 strs[i][j]=strs[0][j]，说明这一列的字母缺失或者不全一样，那么最长公共前缀的长度等于 j，返回 strs[0] 的长为 j 的前缀。

如果没有中途返回，说明所有字符串都有一个等于 strs[0] 的前缀，那么最长公共前缀就是 strs[0]。

作者：灵茶山艾府

链接：https://leetcode.cn/problems/longest-common-prefix/solutions/2801713/jian-dan-ti-jian-dan-zuo-pythonjavaccgoj-478q/

来源：力扣（LeetCode）

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution {
    public String longestCommonPrefix(String[] strs) {
        String s0 = strs[0]; // 初始共同前缀设为整个第一给单词，按它的字符一列一列比对
        // j：代表【列号】，从左往右，第0列、第1列、第2列...
        for (int j = 0; j < s0.length(); j++) {
            char c = s0.charAt(j); //// 基准字符串第 j 列的字符
            for (String s : strs) { // 从上到下，遍历数组里每一个字符串 s（每一行）
                // 两个条件满足任意一个，就代表公共前缀到此为止
                // 条件1：j == s.length() → 当前字符串长度不够，没有第j列字符了
                // 条件2：s.charAt(j) != c → 当前字符串第j列字符和基准不一样
                if (j == s.length() || s.charAt(j) != c) {
                    // substring(0,j)：截取 [0,j)，也就是0~j-1，正好是前面匹配成功的前缀
                    return s0.substring(0, j);
                }
            }
        }
        // 如果循环跑完了都没return，说明第一个字符串本身就是全部公共前缀
        return s0;
    }
}

‍