「力扣」14. 最长公共前缀

题目描述

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

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

示例 1：

输入：strs = ["flower","flow","flight"]
输出："fl"

示例 2：

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

提示：

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i] 仅由小写英文字母组成

题解

横向扫描

我们可以使用横向扫描的方式，数组中两个字符串先进行比较，得到一个最大公共子串，然后再将得到的这个最大公共子串和数组中后面的字符串继续比较，如下图：

在比较的过程中，如果得到最大公共前缀是空字符串，可提前结束循环。

题目中说明，字符串数组不可能是空的，并且里面的子串也不可能是空的，所以无需判断他们的边界条件。

class Solution {
    public String longestCommonPrefix(String[] strs) {
        String maxPrefix = strs[0]; // 最大公共前缀，初始的时候默认认为是数组的第一个元素
        for (int i = 1; i < strs.length; i++) { // 数组遍历从1开始
            int minLength = Math.min(strs[i].length(), maxPrefix.length()); // 两个字符串遍历只需要遍历到最小长度 - 1 即可
            StringBuilder prefix = new StringBuilder(); // 两个字符串中的字符要逐个比较，如果相同则放入prefix中，否则跳出循环。
            int j = 0;
            while (j < minLength) {
                if (maxPrefix.charAt(j) != (strs[i].charAt(j))) { // 不相同则跳出循环
                    break;
                }
                prefix.append(strs[i].charAt(j)); // 相同的时候将其放入prefix中。
                j++; // 指针自增
            }
            maxPrefix = prefix.toString(); // 每次得到的结果赋值给maxPrefix，供后续继续对比
        }
        return maxPrefix; // 返回最大公共子串
    }
}

提交到力扣结果如下：

上述代码中这种横向扫描方式的时间复杂度是O(mn)， 空间复杂度是O(n)，不过其实可以将空间复杂度缩小，考虑下空间复杂度为什么是O(n)，是因为StringBuilder prefix = new StringBuilder();这段代码存储了字符而已，我们不存储最大公共前缀这些字符，考虑下其实j就是最大公共字符的最大索引，所以可以直接使用字符串截取获得最大公共前缀，而无需存储。

public String longestCommonPrefix(String[] strs) {
    String maxPrefix = strs[0]; // 最大公共前缀，初始的时候默认认为是数组的第一个元素
    for (int i = 1; i < strs.length; i++) { // 数组遍历从1开始
        int minLength = Math.min(strs[i].length(), maxPrefix.length()); // 两个字符串遍历只需要遍历到最小长度 - 1 即可
        int j = 0;
        while (j < minLength) {
            if (maxPrefix.charAt(j) != (strs[i].charAt(j))) { // 不相同则跳出循环
                break;
            }
            j++; // 指针自增
        }
        maxPrefix = maxPrefix.substring(0, j); // 截取字符串得到maxPrefix，供后续继续对比
    }
    return maxPrefix; // 返回最大公共子串
}

再次提交到力扣查看结果：

可以看到空间复杂度变为了O(1)。

纵向扫描

我们也可以使用纵向扫描的方式，每个字符串取出来索引位置相同的字符进行对比，效果图如下：

我们仔细研究下思路：

我们需要定义一个变量i用于表示字符索引的位置，它从0开始，到什么地方结尾呢？数组中每个字符串的长度是不同的呀，如果能找到最小的那个字符串是最好的，因为最大公共前缀的长度肯定不会大于数组中长度最小的字符串的长度，我们可以先计算出来这个长度，比如上面这个示例中最小长度就是4。

图中红色部分，比如我通过下面这种方式获得最短字符串长度：

int minLength = strs[0].length();
for (int i = 1; i < strs.length - 1; i++) {
    minLength = Math.min(minLength, strs[i].length());
}

得到最小长度后，我们就可以通过该长度循环，然后对比每个索引位置的字符是否相等。

for (int i = 0; i < minLength; i++) {
    char c = strs[0].charAt(i); // 代表1行的第一个字符
    for (int j = 1; j < strs.length; j++) { // 第二行开始后的所有字符串
        if (strs[j].charAt(i) != c) { // 如果当前索引对应的字符不相等，则提前结束循环，得到最大公共前缀。
            return strs[0].substring(0, i);
        }
    }
}

当出现不匹配的时候直接截取字符串返回，如果都匹配呢，则直接返回strs[0].substring(0, minLength)，完整代码如下：

public String longestCommonPrefix(String[] strs) {
    int minLength = Integer.MAX_VALUE;
    for (int i = 0; i < strs.length; i++) {
        minLength = Math.min(minLength, strs[i].length());
    }
    for (int i = 0; i < minLength; i++) {
        char c = strs[0].charAt(i); // 代表1行的第一个字符
        for (int j = 1; j < strs.length - 1; j++) { // 第二行开始后的所有字符串
            if (strs[j].charAt(i) != c) { // 如果当前索引对应的字符不相等，则提前结束循环，得到最大公共前缀。
                return strs[0].substring(0, i);
            }
        }
    }
    return  strs[0].substring(0, minLength);
}

提交到力扣查看下：

时间复杂度是O(mn)， 空间复杂度是O(1)。

其实我们也可以不先计算出来最小长度，当我们两行之间判断的时候，如果指针已经等于某个字符串的长度，那么也截取字符串并返回也是可以的。

public String longestCommonPrefix(String[] strs) {
    for (int i = 0; i < strs[0].length(); i++) {
        char c = strs[0].charAt(i); // 代表1行的第一个字符
        for (int j = 0; j < strs.length; j++) { // 第二行开始后的所有字符串
            if (i == strs[j].length() || strs[j].charAt(i) != c) { // 如果当前索引对应的字符不相等，则提前结束循环，得到最大公共前缀。
                return strs[0].substring(0, i);
            }
        }
    }
    return  strs[0];
}

提交到力扣：

时间复杂度是O(mn)， 空间复杂度是O(1)。