Rearch Interest: Visualization">
14. 最长公共前缀
题目描述
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例 1: >输入: ["flower","flow","flight"] >输出:
"fl"
示例 2: >输入: ["dog","racecar","car"] >输出:
"" >解释: 输入不存在公共前缀。
提示：
1 <= strs.length <= 2000 <= strs[i].length <= 200strs[i]仅由小写英文字母组成
我的代码
\(T(M,N) = O(MN)\), \(S(N) = O(1)\)
{.line-numbers} 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
class MySolution14
{
public String longestCommonPrefix(String[] strs)
{
String pre = "";
if (strs.length<=0) return "";
boolean flag = true;
for (int i=0; flag; i++)
{
if (i>=strs[0].length()) break;
char ch = strs[0].charAt(i);
for (int j=0; j<strs.length; j++)
{
if (i>=strs[j].length()||ch!=strs[j].charAt(i))
{
flag = false; break;
}
}
if (flag)
pre+=ch+"";
}
return pre;
}
}
1 | class MySolution14 |
方法一: 分治法
\(T(M,N) = O(M,N)\), \(S(M,N) = O(MlogN)\)
注意到LCP的计算满足结合律，有以下的结论： \[LCP(S_1...S_n)=LCP(LCP(S_1...S_k),LCP(S_{k+1}...S_n))\]
其中\(LCP(S_1...S_n)\)是字符串\(S_1...S_n\)的最长公共前缀, \(1 < k < n\)。
基于上述结论，可以使用分治法得到字符串数组中的最长公共前缀： 将问题\(LCP(S_i...S_j)\)分解为两个子问题: \(LCP(S_i...S_{mid})\)和\(LCP(S_{mid+1}...S_j)\)，其中\(mid=\frac {i+j}{2}\). 对两个子问题分别求解，然后对两个子问题的解计算最长公共前缀，即为原问题的解。
时空复杂度：
- \(T(M,N) = O(MN)\)，其中\(M\)是
strs数组中字符串的平均长度，\(N\)是字符串的数量； 递推式: \(T(N)=2·T(\frac N2)+O(M)\). - \(S(M,N) = O(MlogN)\)，其中\(M\)是
strs数组中字符串的平均长度，N是字符串的数量； 主要取决于递归调用的层数，层数最大为\(logN\)，每层需要\(M\)的空间来存储返回结果。
{.line-numbers} 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
class Solution14
{
public String longestCommonPrefix(String[] strs)
{
if (strs==null||strs.length==0) return "";
else return longestCommonPrefix(strs, 0, strs.length-1);
}
public String longestCommonPrefix(String[] strs, int start, int end)
{
if (start==end) return strs[start];
int mid = start+(end-start)/2;
String lcpLeft = longestCommonPrefix(strs, start, mid);
String lcpRight = longestCommonPrefix(strs, mid+1, end);
return commonPrefix(lcpLeft, lcpRight);
}
public String commonPrefix(String lcpLeft, String lcpRight)
{
int minLength = Math.min(lcpLeft.length(), lcpRight.length());
for (int i=0; i<minLength; i++)
if (lcpLeft.charAt(i)!=lcpRight.charAt(i))
return lcpLeft.substring(0,i);
return lcpLeft.substring(0,minLength);
}
}
1 | class Solution14 |
方法二: 二分查找
\(T(M,N) = O(MNlogM)\), \(S(M,N) = O(1)\)
显然，最长公共前缀的长度不会超过字符串数组strs中最短字符串的长度minLength。 可以在[0,minLength]的范围内通过二分查找得到最长公共前缀的长度。
每次取查找范围的中间值mid，判断每个字符串的长度为mid的前缀是否相同。 若相同，则最长公共前缀的长度一定大于等于mid； 否则，最长公共前缀的长度一定小于mid； 通过上述方式每次将查找范围缩小一半，直到得到最长公共前缀的长度。
时空复杂度：
- \(T(M,N) = O(MNlogM)\)，其中\(M\)是
strs数组中字符串的平均长度，\(N\)是字符串的数量； 二分查找的迭代执行次数是\(O(logM)\)，每次迭代最多需要比较\(MN\)个字符，因此总的时间复杂度是\(O(MNlogM)\)。 - \(S(M,N) = O(1)\)。
1 | class Solution14 |