Leetcode之14-最长公共前缀(Longest Common Prefix)

算法题

题干

编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀, 返回空字符串。

示例

1
2
3
4
5
6
7
8
示例 1:
输入: ["flower","flow","flight"]
输出: "fl"

示例 2:
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。

说明

所有输入只包含小写字母a-z。

思路

本题求解最长公共前缀, 首先明确一点是最长公共前缀同样也是数组中最短字符串的前缀。因此我们可以先对数组字符串按照字符串长度升序排序, 然后以第一个元素为标准, 循环遍历第一个元素获取所有前缀, 然后判断原字符串数组中的元素是否以这些前缀开头。
当然也可以不用排序, 直接按照第一个元素为标准, 看后续元素是否以第一个元素开头, 如果不是, 截取第一个元素前length-1位, 再判断后续元素是否以截取后的字符串开头, 如果依旧不是, 重复上述过程。

Java代码

解法1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length <= 0) {
return "";
}
Arrays.sort(strs, Comparator.comparingInt(String::length));
final int FIRST_ELE_LEN = strs[0].length();
final int ARRAY_LEN = strs.length;
String longestCommonPrefix = "";
outer:
for (int i = 1; i <= FIRST_ELE_LEN; i++) {
String temp = strs[0].substring(0, i);
boolean beSamePrefix = true;
for (int k = 1; k < ARRAY_LEN; k++) {
beSamePrefix = temp.equals(strs[k].substring(0, i)) && beSamePrefix;
if(!beSamePrefix) {
break outer;
}
}
longestCommonPrefix = temp;
}
return longestCommonPrefix;
}

代码解析

  1. 第5行代码是将字符串数组按照字符串长度进行升序排列。
  2. 第11行代码代表temp变量表示排序后数组第一个元素的前缀。
  3. 第12行代码代表beSamePrefix变量表示排序后第二个及之后的所有元素是否以temp变量开头。
  4. 第15-17行代码表示只要中间一次不是按照temp开头, 表明前一个temp变量(即当前longestCommonPrefix变量)即最长公共前缀, 直接break即可。这个break是跳出外层for循环, 即没必要继续进行后续前缀的比较。

解法2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length <= 0) {
return "";
}
String prefix = strs[0];
for (int i = 1, len = strs.length; i < len; i++) {
while (!strs[i].startsWith(prefix)) {
prefix = prefix.substring(0, prefix.length() - 1);
}
if (prefix == null || "".equals(prefix)) {
return "";
}
}
return prefix;
}

代码解析

  1. 第7-9行代码表示找出以prefix变量值为前缀的最长前缀。

思考题

  1. 是否还有其他更加优雅/复杂度更低的解法?
如果有任何错误或疑问, 欢迎小伙伴们评论区留言^-^
( 完 )

欢迎各位看官关注

麻辣烫,走起
0%