【算法攻坚】最长公共前缀

发表于

这是我参与11月更文挑战的第16天，活动详情查看：2021最后一次更文挑战

今日题目

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

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

示例 1：

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

示例 2：

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

提示：

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

思路

公共最长前缀的特点： 前缀必然存在每一个字符串。

使用第一个字符串与其他字符串进行逐一对比得出前缀长度；并且所有长度取最小值就是题解

可优化的点：

  1. 公共前缀不会超过任意一个字符串的长度，不用每次都比较整个字符串，只要比较当前的前缀长度即可
  2. 如果没有公共前缀，那么不需要遍历剩余的字符串

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
java复制代码public String longestCommonPrefix(String[] strs) {
    if (strs.length == 0) {
        return "";
    }
    // 最长前缀末尾位置
    int end = strs[0].length() - 1;
    for (int i = 1; i < strs.length; i++) {
        // 优化1: 不用比较整个字符串, 只要比较前缀长度即可
        int j = 0;
        for (; j <= end && j < strs[i].length(); j++) {
            if (strs[0].charAt(j) != strs[i].charAt(j)) {
                //如果第一个字符都不相等，就不用比较了
                if(j == 0){
                    return "";
                }
                break;
            }
        }
        end = Math.min(end, j - 1);
    }
    return strs[0].substring(0, end + 1);
}

执行用时：1 ms, 在所有 Java 提交中击败了70.59%的用户

内存消耗：36.3 MB, 在所有 Java 提交中击败了89.59%的用户

解法二

第二种解法其实和第一种是一样的思想，只不过可以利用String的api方法

startWith()方法，有了这个方法可以使代码实现更加优雅

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
java复制代码 public String longestCommonPrefix(String[] strs) {
     if (strs.length == 0) {
         return "";
     }
     // 最长前缀
     String commonPrefix = strs[0];
     for (int i = 1; i < strs.length; i++) {
         while (!strs[i].startsWith(commonPrefix)) {
             if (commonPrefix.length() == 0) {
                 return "";
             }
             commonPrefix = commonPrefix.substring(0, commonPrefix.length() - 1);
         }
     }
     return commonPrefix;
 }

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户

内存消耗：36.5 MB, 在所有 Java 提交中击败了44.26%的用户

小结

这两天的题目相对来说比较简单，但是能够一次完全写对还是有难度的，需要多注意常用的api写法

比如：

  • map的循环方式，entry的写法
  • String的常用api，比如substring(start, end)注意不是驼峰, 区间是左闭右开**[start, end)**
  • 字符串和链表获取串长度是方法ss.length()，而数组的是变量array.length
  • 数字与字符串之间的互转，String.valueOf(int), Integer.parseIn(string)这个方法不会频繁拆箱装箱
  • 而且做题有注意审题，这道题我刚开始还以为是找最长公共子串

今天多学一点知识，明天就少说一句求人的话

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%