最长公共前缀

14. 最长公共前缀 easy

编写一个函数来查找字符串数组中的最长公共前缀。
Write a function to find the longest common prefix string amongst an array of strings.

如果不存在公共前缀，返回空字符串 ""。
If there is no common prefix, return an empty string "".

这玩意也有很多种解法
用 $ LCP(S_1,...,S_n) $表示最长公共前缀, 有结合律:

$$LCP(S_1,...,S_n)=LCP(LCP(LCP(S_1,S_2),S_3)...,S_n)$$

同样, 根据结合律也可以分治, 降低树的高度
不过, 直接纵向扫描才是最简单的

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) return "";
        StringBuilder sb = new StringBuilder();
        int idx = 0;
        while (step(strs, idx)) {
            sb.append(strs[0].charAt(idx));
            idx++;
        }
        return sb.toString();
    }

    private boolean step(String[] strs, int idx) {
        if (idx >= strs[0].length()) return false;
        char c = strs[0].charAt(idx);
        for (String s : strs) {
            if (idx >= s.length() || s.charAt(idx) != c) return false;
        }
        return true;
    }
}