LeetCode 14. Longest Common Prefix
Problem
LeetCode 14. Longest Common Prefix
1. 题目简述
给出一组字符串，找出这些字符串的最长common前缀。
2. 算法思路
水平比较
首先，最容易想到的思路就是从前往后，一个个进行比较找common suffix，直到找到最后一个字符串。
这种方法时间复杂度为O(S)，S是所有字符串的字符数总和，最坏情况就是所有字符串相等，一直比较下去。
垂直比较
垂直的意思是从第一位开始比较，比较所有的字符串的第一位，如果相同，则比较下一位；如果不同或者到达某字符串的最大长度，则返回当前的suffix。
这种方法时间复杂度为O(S)，S是所有字符串的字符数总和，最坏情况就是所有字符串相等，一直比较下去。
分治法
可以将原本的数组不断拆分成子数组，然后获取子数组的最长公共前缀，然后再进行合并。
时间复杂度为O(S),空间复杂度为O(m * logn)。空间复杂度是因为我们需要调用函数logn词，每次空间为m。
3. 解法
水平比较
1
2
3
4
5
6
7
8
9
10
11
12
13
|
public class Solution {
public String longestCommonPrefix(String[] strs) {
if (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.isEmpty()) return "";
}
return prefix;
}
}
|
垂直比较
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public class Solution {
public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) return "";
for (int i = 0; i < strs[0].length() ; i++){
char c = strs[0].charAt(i);
for (int j = 1; j < strs.length; j ++) {
if (i == strs[j].length() || strs[j].charAt(i) != c)
return strs[0].substring(0, i);
}
}
return strs[0];
}
}
|
分治法
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
| class Soluton{
public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) return "";
return longestCommonPrefix(strs, 0 , strs.length - 1);
}
private String longestCommonPrefix(String[] strs, int l, int r) {
if (l == r) {
return strs[l];
}
else {
int mid = (l + r)/2;
String lcpLeft = longestCommonPrefix(strs, l , mid);
String lcpRight = longestCommonPrefix(strs, mid + 1,r);
return commonPrefix(lcpLeft, lcpRight);
}
}
String commonPrefix(String left,String right) {
int min = Math.min(left.length(), right.length());
for (int i = 0; i < min; i++) {
if ( left.charAt(i) != right.charAt(i) )
return left.substring(0, i);
}
return left.substring(0, min);
}
}
|
