14.最长公共前缀

纵向扫描

最长公共前缀的含义，就是所有字符串在前若干个位置上的字符都相同，因此可以按列来检查。

先求出所有字符串中的最短长度，因为公共前缀长度不可能超过它。随后从第 $0$ 列开始依次判断，取第一个字符串当前位置的字符作为基准，再和其余字符串同一位置的字符比较。如果某一列出现不同字符，说明公共前缀到此为止；否则就把该字符加入答案。

时间复杂度 $O(nm)$

空间复杂度 $O(1)$

class Solution {
    public String longestCommonPrefix(String[] strs) {
        int minLen = Integer.MAX_VALUE;
        for (String s : strs) {
            minLen = Math.min(minLen, s.length());
        }
        int n = strs.length;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < minLen; ++i) {
            char cur = strs[0].charAt(i);
            boolean flag = true;
            for (int j = 1; j < n; ++j) {
                if (strs[j].charAt(i) != cur) {
                    flag = false;
                }
            }
            if (!flag) {
                break;
            }
            sb.append(cur);
        }
        return sb.toString();
    }
}

以第一个字符串为基准

也可以直接把第一个字符串当作候选答案。

遍历第一个字符串的每一个位置，检查其余所有字符串在该位置是否也存在且字符相同。只要某个字符串已经到头，或者当前位置字符不同，就说明公共前缀只能到当前位置之前，直接返回第一个字符串的前缀即可。

这种写法本质上也是纵向扫描，只是省去了额外统计最短长度的过程。

时间复杂度 $O(nm)$

空间复杂度 $O(1)$

class Solution {
    public String longestCommonPrefix(String[] strs) {
        int n = strs.length;
        String first = strs[0];
        for (int i = 0; i < first.length(); ++i) {
            char cur = first.charAt(i);
            for (String s : strs) {
                if (i == s.length() || s.charAt(i) != cur) {
                    return first.substring(0, i);
                }
            }
        }
        return first;
    }
}