题目描述
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例 1：
1
2
| 输入：strs = ["flower","flow","flight"]
输出："fl"
|
示例 2：
1
2
3
| 输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。
|
提示：
1 <= strs.length <= 2000 <= strs[i].length <= 200strs[i] 仅由小写英文字母组成
题解
我们可以每两个进行比较，得到这两个的最长公共前缀后，再跟后面的字符串进行比较，以此类推，如下图所示：
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
| class Solution {
public String longestCommonPrefix(String[] strs) {
String s1 = strs[0];
for (int i = 1; i < strs.length; i++) {
String min = longestCommonPrefix(s1, strs[i]);
s1 = s1.length() > min.length() ? min : s1;
if (s1 == "") {
break;
}
}
return s1;
}
private String longestCommonPrefix(String s1, String s2) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < Math.min(s1.length(), s2.length()); i++) {
if (s1.charAt(i) != s2.charAt(i)) {
break;
}
sb.append(s1.charAt(i));
}
return sb.toString();
}
}
|
提交结果如下：
看过题解后，看到官方提供的横向扫描与我的思路是一致的，使用官方代码执行后发现，击败了100%的人，对比后发现，在计算两个字符串的最大公共前缀时，他是先计算索引，最后再截取字符串，而我是是采用的StringBuilder的append方法。
将我的代码修改下：
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
| class Solution {
public String longestCommonPrefix(String[] strs) {
String s1 = strs[0];
for (int i = 1; i < strs.length; i++) {
String min = longestCommonPrefix(s1, strs[i]);
s1 = s1.length() > min.length() ? min : s1;
if (s1 == "") {
break;
}
}
return s1;
}
private String longestCommonPrefix(String s1, String s2) {
int index = 0;
for (int i = 0; i < Math.min(s1.length(), s2.length()); i++) {
if (s1.charAt(i) != s2.charAt(i)) {
break;
}
index++;
}
return s1.substring(0, index);
}
}
|
再次提交：
官方还提供了很多方法！！！