最长公共前缀（Leetcode14）

例题：

分析：

我们可以先定义两个变量 i ，?j， j表示数组中的每一个字符串， i 表示每个字符串中的第几个字符。一列一列地进行比较，先比较第一列的字符，若都相同，则 i ++ ，继续比较第二列的字符。直至出现不匹配的字符。

这样比较会出现以下3种情况，需要分开处理。

情况1：比较某一列时，遇到不同字符， i 之前的字符就是解。

情况2：比较某一列时，遇到字符串长度不够，i 之前的字符就是解。

情况3：i 循环自然结束，此时第一个字符串就是解。

我们可以都用第一个字符串作为返回的模板。

代码实现：

public class LCPLeetcode14 {

    /*
    * 情况1：比较某一列时，遇到不同字符，i 之前的字符就是解
    * 情况2：比较某一列时，遇到字符串长度不够，i 之前的字符就是解
    * 情况3：i 循环自然结束，此时第一个字符串就是解
    * */
    public static String longestCommonPrefix(String[] strs) {
        char[] first = strs[0].toCharArray();
        for (int i = 0; i < first.length; i++) {
            char ch = first[i];
            for (int j = 1; j < strs.length; j++) { //从二行开始比对，因为第一行字符已被拿到
                //情况2必须先校验，遍历字符串时，如果长度不够会发生索引越界
                if(strs[j].length() == i || ch != strs[j].charAt(i)){  //情况1、情况2合并
                    return new String(first, 0, i);
                }
            }
        }
        return strs[0];
    }

    public static void main(String[] args) {
        System.out.println(longestCommonPrefix(new String[]{"flower", "flow", "flight"})); // fl
        System.out.println(longestCommonPrefix(new String[]{"dog","racecar","car"})); //
        System.out.println(longestCommonPrefix(new String[]{"ab","a"})); // a
        System.out.println(longestCommonPrefix(new String[]{"dog","dogaa","dogbb"})); // dog
    }
}