描述
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 “”。
示例 1:
输入: [“flower”,”flow”,”flight”]
输出: “fl”
示例 2:
输入: [“dog”,”racecar”,”car”]
输出: “”
解释: 输入不存在公共前缀。
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
|
class Solution {
public String longestCommonPrefix(String[] strs) {
//if(strs==null) return null;
int N=strs.length;
int maxlen=0;
int maxflag=0;
for(int i = 0; i<N;i++)
{
if(strs[i].length()>maxlen)
{
maxlen=strs[i].length();
maxflag=i;
}
}
List<Character> list=new ArrayList<>();
for(int i = 0;i<maxlen;i++)
{
list.add(strs[maxflag].charAt(i));
}
int num=0; //第num个元素
int min =maxlen; //子字符串截取尾指针
for(int i =0;i<strs.length;i++)
{
String str = strs[i];
int n = str.length();
if(n==0) return "";
for(int j=0;j<n;j++)
{
if(str.charAt(j)==list.get(j))
{
if(j==n-1 && n< min)
{
min = n;
num=i;
}
}else {
if(j>0 && j<min)
{
min = j;
num=i;
break;
}else if(j == 0) return "";
}
}
}
//System.out.println(num);
//System.out.println(min);
if(strs.length==0) return "";
else{
String string = strs[num];
//return string.substring(0,min);
return string.length()==0?"":string.substring(0,min);
}
}
}
|
方法二：
暴力法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
class Solution {
public String longestCommonPrefix(String[] strs) {
if (strs.length == 1){
return strs[0];
}
StringBuilder sb = new StringBuilder();
if (strs.length>1) {
int len = strs[0].length();
for (int i = 0; i < len; i++) {
char curr = strs[0].charAt(i);
for (int j = 1; j < strs.length; j++) {
if (strs[j].length()<=i ||strs[j].charAt(i) != curr) {
return sb.toString();
}
if (strs[j].charAt(i) == curr && j == strs.length - 1) {
sb.append(curr);
}
}
}
}
return sb.toString();
}
}
|
近期评论