【leetcode】14：最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

示例 1:

输入: ["flower","flow","flight"]
输出: "fl"
示例 2:

输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。

说明:

所有输入只包含小写字母 a-z 。

解答

这道题还是比较简单的，不过简单的题，虽然你会做，不代表你能做的好。我觉得很多人可能会这样做：

1、先找出 str1 和 str2（注：str1代表第一个字符串，str2代表第二个） 的公共字符串 s1。

2、然后再找出 s1 和 str3 的公共前缀 s2。

3、然后再找出 s2 和 str4 的公共前缀 s3。

4、一直这样遍历重复，用一个变量来保存两个两个字符串之间的公共前缀。

这种方法应该是最容易想到的了，不过并不是特别好，其实我们可以这样做：我们不横向一个一个字符串遍历，而是采用纵向的方式。例如对于这个["flower","flow","flight"]。我们把它看成一个二维字符数组

f l o w e r
f l o w
f l i g h t

然后纵向遍历，一列一列遍历，只要发现某一列出现不同的字符，就遍历结束，例如上面这个例子中，第三列就出现不同了，所以遍历结束，把前两列返回。代码如下：

    public static String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length <= 0) {
            return "";
        }
        String s = "";
        for (int j = 0; j < strs[0].length(); j++) {
            char c = strs[0].charAt(j);
            // 开始纵向遍历
            for (int i = 1; i < strs.length; i++) {
                if (j >= strs[i].length() || c != strs[i].charAt(j)) {
                    return s;
                }
            }
            s += c;
        }
        return s;
    }

往期

二维码