LeetCode-Longest Common Prefix

https://leetcode.com/problems/longest-common-prefix

最长前缀匹配问题,最直观的思路的程序如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
def longestCommonPrefix(self, strs):
"""
:type strs: List[str]
:rtype: str
"""
prefix=''
if len(strs)>0:
minLen=min(map(lambda x:len(x),strs))
for i in range(minLen):
s=strs[0][i]
addFlag=True
for str in strs:
if str[i]!=s:
addFlag=False
break
if addFlag:
prefix=prefix+s
else:
break
return prefix

用时 39ms

使用 Java,不进行字符串的不断截取,只进行前缀长度的记录,并且将边界情况直接用 if 进行排除。

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 Solution {
public String longestCommonPrefix(String[] strs) {
if(strs.length==0){
return "";
}else if(strs.length==1){
return strs[0];
}
int prefix_len=strs[0].length();
for(int i=1;i<strs.length;i++){
if(strs[i].length()<prefix_len){
prefix_len=strs[i].length();
}
for(int j=0;j<prefix_len;j++){
if((strs[i].charAt(j)!=strs[0].charAt(j))){
prefix_len=j;
break;
}
}
if(prefix_len==0){
return "";
}
}
return strs[0].substring(0,prefix_len);
}
}

用时少于 85.96%的人。

看了一下官方的标准答案,除了我这里 Python 和 Java 代码中所用的思想以外,还有二分查找、分治和建树的思想,其中二分查找有将字符串集合二分和将单个字符串进行二分,这些思想非常重要。

使用二分法进行查找的方法如下:

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
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
if (strs.size()==0) return "";
else if(strs.size()==1) return strs[0];
int len = helper(strs);
return strs[0].substr(0,len);
}

int helper(vector<string>& strs) {
int mid = strs.size()/2;
return getCommonPrefix(strs[0], helper(strs, 0, mid), strs[mid], helper(strs, mid, strs.size()));
}

int helper(vector<string>& strs, int left, int right) {
if(right-left == 1) return strs[left].size();
else if (right-left == 2) return getCommonPrefix(strs[left], strs[left].size(), strs[left+1], strs[left+1].size());
int mid = (left+right)/2;
return getCommonPrefix(strs[left], helper(strs, left, mid), strs[mid], helper(strs, mid, right));
}

int getCommonPrefix(string& s1, int len1, string& s2, int len2) {
int maxLen = min(len1, len2);
int commonLen = 0;
for(int i=0; i<maxLen; ++i) {
if(s1[i]==s2[i]) commonLen++;
else break;
}
return commonLen;
}
};