14. 最长公共前缀
题目
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例
输入: ["flower","flow","flight"]
输出: "fl"
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
1
2
3
4
5
6
2
3
4
5
6
说明
所有输入只包含小写字母 a-z
我的思路
- 判断特殊情况，并直接返回。
- 取第一个字符串，循环每个字符，匹配所有字符串，。
- 遇到字符串长度小于等于前缀或者字符串对应位置上不等于最后一个前缀，返回前缀。
- 没有遇到 3的情况，前缀就再末尾加上新的字符，最后返回前缀。
Java源码
class Solution {
public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0)
return "";
if (strs.length == 1)
return strs[0];
String first = strs[0];
String dff = "";
for (int i = 0; i < first.length(); i++) {
char c = first.charAt(i);
for (int j = 1; j < strs.length; j++) {
if (strs[j].length() <= dff.length() || strs[j].charAt(i) != c) {
return dff;
}
}
dff = dff + c;
}
return dff;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
Dart源码
String longestCommonPrefix(List<String> strs) {
if (strs == null || strs.length == 0)
return "";
if (strs.length == 1)
return strs[0];
String first = strs[0];
String dff = "";
for (int i = 0; i < first.length; i++) {
String c = first.substring(i,i+1);
for (int j = 1; j < strs.length; j++) {
if (strs[j].length <= dff.length || strs[j].substring(i,i+1) != c) {
return dff;
}
}
dff = dff + c;
}
return dff;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
推荐方案
将数组的第一个字符串，作为前缀，和第二进行比较，找到相同的前缀；再使用该前缀继续和其他字符串进行比较
Java源码
public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0)
return "";
String prefix = strs[0];
for (int i = 1; i < strs.length; i++) {
while (strs[i].indexOf(prefix) != 0) {
prefix = prefix.substring(0, prefix.length() - 1);
if (prefix.length() == 0) {
return "";
}
}
}
return prefix;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Dart源码
String longestCommonPrefix(List<String> strs) {
if (strs == null || strs.length == 0)
return "";
String prefix = strs[0];
for (int i = 1; i < strs.length; i++) {
while (strs[i].indexOf(prefix) != 0) {
prefix = prefix.substring(0, prefix.length - 1);
if (prefix.length == 0) {
return "";
}
}
}
return prefix;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
优化点
- 减少了一个dff空间开辟