LeetCode【14、最长公共前缀】（简单）

发表于

题目描述

这是 LeetCode 上的 14. 最长公共前缀，难度为 简单。

关键字： 字符串

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

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

示例 1：

1
2
ini复制代码输入：strs = ["flower","flow","flight"]
输出："fl"

示例 2：

1
2
3
ini复制代码输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。

提示：

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

划重点

  1. 不存在返回空字符串

解题思路

方法1：

我们可以遍历字符数组，每次拿到两个字符串获取公共前缀，再用这个公共前缀与下一个字符串进行比较获取新的公共前缀，一直到最后得到的就是所有字符串的最长公共前缀。一旦没有公共前缀可以返回空、不需要再比较后面的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
java复制代码class Solution {
    public String longestCommonPrefix(String[] strs) {
        // 特殊情况判断
        int len = strs.length;
        String first = strs[0];
        if (len == 1) {
            return first;
        }
        // 定义最小公共前缀
        String ans = first;
        for (int i = 1; i < len; i++) {
            ans = getPrefix(ans, strs[i]);
            if (ans.length() == 0) {
                break;
            }
        }
        return ans;
    }

    public String getPrefix(String s1, String s2) {
        int len = Math.min(s1.length(), s2.length());
        int index = 0;
        while (index < len && s1.charAt(index) == s2.charAt(index)) {
            ++index;
        }
        return s1.substring(0, index);
    }
}
  • 时间复杂度：O(mn)
  • 空间复杂度：O(1)

方法2：

对于一个字符数组取最长公共前缀，我们可以将其看作一个二维的字符数组，每一个字符串就是一个字符数组。所以可以对每一个字符串的同一位进行比较，如果都相同则添加该字符到最长公共前缀中，一旦有一个不同的直接返回。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
java复制代码class Solution {
    public String longestCommonPrefix(String[] strs) {
        String ans = "";
        int len = strs.length;
        String first = strs[0];
        if (len == 1) {
            return first;
        }
        for (int i = 0; i < 200; i++) {
            // 判断当前遍历的位数是不是超过第一个字符串的长度，超过或者正好则直接返回
            if (i >= first.length()) {
                return ans;
            }
            // 获取第一个字符串所的遍历到的位的值
            char c = first.charAt(i);
            for (int j = 1; j < len; j++) {
                // 超出长度或者和当前字符不同则返回
                if (i >= strs[j].length() || strs[j].charAt(i) != c) {
                    return ans;
                }
            }
            // 符合条件则将当前字符拼到最长公共前缀
            ans += String.valueOf(c);
        }
        return ans;
    }
}
  • 时间复杂度：O(mn)
  • 空间复杂度：O(1)

引用

我的 github 仓库已经同步建立，点击访问

本文转载自: 掘金

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

0%