14. 最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 “”。

示例 1：
输入：strs = [“flower”,”flow”,”flight”]
输出：”fl”

示例 2：
输入：strs = [“dog”,”racecar”,”car”]
输出：””
解释：输入不存在公共前缀。

因为是公共前缀，那么每个元素肯定都包含该前缀
假设初始前缀字符串是数组第一个元素，遍历字符串数组，判断前缀字符串是否是字符串的前缀，若都是，则该前缀字符串即公共前缀字符串；
若不是，则截取前缀字符串，缩短一位，再次遍历比较判断，直至前缀字符串是公共前缀或者无法匹配：

public String longestCommonPrefix(String[] strs) {
    if (strs.length == 0) {
        return "";
    }
    // 取数组第一个字符串作为对照
    String base = strs[0];
    // 根据字符串长度从最长子串从后往前遍历
    for(int i = base.length(); i > 0; i--) {
        // 截取字符串作为公共前缀
        String preStr = base.substring(0, i);
        boolean isAllStartWith = true;
        // 判断对照字符串是否是所有的字符串的前缀
        for(int j = 0; j< strs.length; j++) {
            if (!strs[j].startsWith(preStr)) {
                isAllStartWith = false;
            }
        }
        if (isAllStartWith) {
            return preStr;
        }
    }
    return "";
}

也可以同步比较字符串的每一位字符，若相同在向右移动，若不同，则表示已经不是公共前缀：

public String longestCommonPrefix(String[] strs) {
    if (strs == null || strs.length == 0) {
        return "";
    }
    // 前缀字符串
    String base = strs[0];
    for (int i = 0; i < base.length() ; i++){
        // 比较的字符
        char c = base.charAt(i);
        for (int j = 1; j < strs.length; j ++) {
            // 遇到了最短字符串
            if (i == strs[j].length()) {
                // 最长公共前缀
                return base.substring(0, i);
            }
            // 遇到了字符不相同
            if (strs[j].charAt(i) != c) {
                // 最长公共前缀
                return base.substring(0, i);
            }
        }
    }
    // 最长公共前缀
    return base;
}