最长公共前缀

WangScaler: 一个用心创作的作者。

声明：才疏学浅，如有错误，恳请指正。

题目

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

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

分析

初步思考

取第一个字符串的每个字符和其他字符串的每个数组进行对比，如果一样则m++。如果遍历结束m的值和数组的长度一致，则截取当前字符串之前的部分为最长公共前缀，直到不一致时返回。

class Solution {
    public String longestCommonPrefix(String[] strs) {
        String result = "";
        for (int i = 0; i < strs[0].length(); i++) {
            int m = 1;
            result = strs[0].substring(0, i + 1);
            for (int j = 1; j < strs.length; j++) {
                if (i >= strs[j].length()) {
                    return strs[0].substring(0, i);
                }
                if (strs[0].substring(i, i + 1).equals(strs[j].substring(i, i + 1))) {
                    m++;
                }
            }
            if (m != strs.length) {
                return strs[0].substring(0, i);
            }
        }
        return result;
    }
}

我们每一次都是将第一个的字符串和其他几个做了对比才能知道对不对，也就是对比的次数是【（数组的长度-1）*（最大前后缀长度+1）】

里面的equals的底层也是while循环，但是咱们是单个字符串的对比，应该对时间复杂度影响不大。

继续思考

既然知道equals底层是while循环，我们为什么不避免他呢。我们直接使用字符串的charAt(i)，直接比较字符不就行了。为什么截取呢？取消这种无脑截取模式。

将上述的代码if (strs[0].substring(i, i + 1).equals(strs[j].substring(i, i + 1))) 换成if (strs[0].charAt(i)==strs[j].charAt(i))

那么我们的时间复杂度无疑就是O(mn)了。

我看了看答案的横向扫描。先获取前两个字符串的最长公共前缀，然后拿着这个公共前缀和数组的其他字符串对比。那么这个的时间复杂度基本和我们的一致。

从思路看，我们每次至少保证了循环等于最大前缀长度，但是答案的横向扫描却可能多于最大前缀长度。但是执行结果却大大出乎我的意料。

他的执行用时却比我们更少，那么到底是为什么呢？

if (prefix.length() == 0) {break;}当两个对比字符串没有公共长度的时候，直接break，就不和数组后边的进行对比了。优化之后

if (strs[0].charAt(i)==strs[j].charAt(i)){m++;}就变成了if (strs[0].charAt(i)!=strs[j].charAt(i)){break;}m++;

但似乎对结果影响不大。

答案

最后还是给出横向扫描的答案。至于为什么执行的结果，会比我的好，大家帮我看看吧。

 class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        String prefix = strs[0];
        int count = strs.length;
        for (int i = 1; i < count; i++) {
            prefix = longestCommonPrefix(prefix, strs[i]);
            if (prefix.length() == 0) {
                break;
            }
        }
        return prefix;
    }

    public String longestCommonPrefix(String str1, String str2) {
        int length = Math.min(str1.length(), str2.length());
        int index = 0;
        while (index < length && str1.charAt(index) == str2.charAt(index)) {
            index++;
        }
        return str1.substring(0, index);
    }
}

## 复杂度

• 时间复杂度：O(mn)。其中 m 是字符串数组中的字符串的平均长度，n 是字符串的数量。最坏情况下，字符串数组中的每个字符串的每个字符都会被比较一次。
• 空间复杂度：O(1)。在我的题解。只需要常数result和m。在官方题解只需要prefix和count、length和index。

总结

我的解法和官方的解法思路答题是一致的，虽然写法不一样，但是基本是差不多了。但最终性能的区别在哪？望看出的朋友，能给我指导指导，万分感激。

都来了，点个赞再走呗！

关注WangScaler，祝你升职、加薪、不提桶！