一、题目描述

最长公共前缀

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

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

示例 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为计算出的最长前缀。即：

$$
f(x) = g(g(g(str[0],str[1]),str[2])….,str[x])
$$

• 上面公式有点复杂我们稍加变形如下：

$$
f(x+1)=g(x+1,f(x))
$$

• 针对上述的数组我们比对是如下的过程

public String longestCommonPrefix2(String[] strs) {
    if (strs.length == 0) {
        return "";
    }
    String longest = strs[0];
    for (int i = 1; i < strs.length; i++) {
        if (longest.length() == 0) {
            return "";
        }
        longest = longestFromTwo(longest, strs[i]);
    }
    return longest;
}

public String longestFromTwo(String a, String b) {
    int length = Math.min(a.length(), b.length());
    for (int i = 0; i < length; i++) {
        if (a.charAt(i) != b.charAt(i)) {
            return a.substring(0, i);
        }
    }
    return a.substring(0, length);
}

四、总结

• 纵向比较法使我们常用的方式。执行上也是蛮不错的。
• 动态规划可能就有点偏门了。但是这的的确确可以用我之前提到的三板斧动归解题思路解决这个问题。稍加变形就可以了。
• 两种方法各有优缺点。萝卜青菜吧

欢迎关注哦