本文正在参加「Java主题月 – Java 刷题打卡」，详情查看 活动链接

一、题目描述

最长公共前缀

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

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

示例 1：

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

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

二、思路分析

纵向对比法

• 最简单粗暴的方法就是诶个比较，不知道可爱的读者们你们是如何想的，笔者这里第一思路就是每个字符串对应位置进行比较。相同则下一步否则结束。就是简单粗暴。

• 我们将待比较字符排成一队，将按照相同索引进行比较索引上各个字符的内容是否相同，如果相同则加入我们的前缀中。否则结束。图中我们索引进行到2时发现flight中i和前两个不相同，所以最长前缀就是我们0~1的部分fl 。

AC 代码

public String longestCommonPrefix(String[] strs) {
    if (strs.length == 0) {
        return "";
    }
    int minLength = strs[0].length();
    String firstStr = strs[0];
    for (int i = 1; i < strs.length; i++) {
        minLength = Math.min(minLength, strs[i].length());
        if (minLength == 0) {
            return "";
        }
    }
    for (int i = 0; i < minLength; i++) {
        for (int j = 1; j < strs.length; j++) {
            if (firstStr.charAt(i) != strs[j].charAt(i)) {
                return firstStr.substring(0, i);
            }
        }
    }
    return firstStr.substring(0, minLength);
}
复制代码

• 最终效果还算客观的。虽然代码看起来麻烦但是结合我上面的图示理解其实没有多难理解。我们需要借助变量来存储索引方便控制。我们还需要一个变量来用于每次字符串特定索引位置的比较

动态规划法

• 上面比较每个字符串的特定位置理解上很容易，但是代码实现上真的有点绕。从对比方向上我们可以将上述理解成纵向比较法
• 换个角度我们将每个字符串看成一个单体，没两个相邻的字符存在一定的关系。我们试试可不可以从动态规划的角度解决他呢？
• 首先我们令g(a,b)是计算a和b的最长前缀 。f(x)表示数组中截止到x为计算出的最长前缀。即：