题解 | #最长公共前缀#

方法一：子串纵向查找

纵向遍历非常的直观，如下图所示，将每个字符串分别依次遍历每一列的元素，比较相同列上字符是否相同，若相同则比较下一个子串，若不同则最长公共前缀为上个遍历过的公共前缀。

复杂度分析：
时间复杂度：O(mn)，其中n 是字符串的数量，m 是字符串数组中的字符串的平均长度。最坏情况下，字符串数组中的每个字符串的每个字符都会被比较一次。

空间复杂度：O(1)。额外空间复杂度为常数。

演示子串纵向查找方式：

import java.util.*;


public class Solution {

    /**
     * 思路:
     * 对齐数组中所有字符串,然后以数组中第1个字符串为源,其第1个a字符
     * 分别和数组中第2、3、4、5....个字符串的第1个字符开始一一比对
     * 如:
     * abca
     * abc
     * abca
     * abc
     * abcc
     * 5列字符串的第一个字符a都是对应的上的,那么接下来
     *
     * 以数组中第1个字符串为源,其第2个b字符,分别和数组中第2、3、4、5....个字符串的第2个字符开始一一比对
     * 5列字符串的第2个字符b都是对应的上的,那么接下来
     * ....循环
     */
    public String longestCommonPrefix (String[] strs) {

        if (strs.length == 0) {
            return "";
        }

        for (int i = 0; i < strs[0].length(); i++) {

            char source = strs[0].charAt(i);

            for (int j = 1; j < strs.length; j++) {

                // abca为源 发现和数组中第二个字符串abc都比较完成后, 源对象开始是数组下标为3的a字符了,此时发现abc是最长公共前缀,应立即截断返回
                if (strs[j].length() <= i) {
                    return strs[0].substring(0, i);
                }

                char target = strs[j].charAt(i);

                if (source != target) {
                    return strs[0].substring(0, i);
                }
            }
        }

        //如果abc abc情况 默认返回strs[0]
        return strs[0];
    }
}