JYT's Leetcode Solution(3)
2022-07-27
1 题目描述
题14 最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串””。
示例1
1 | 输入：strs = ["flower","flow","flight"] |
示例2
1 | 输入：strs = ["dog","racecar","car"] |
2 问题解法
2.1 显而易见的办法
乍一看，我们很容易想到比较字符串数组中各字符串的第一个字符，若全部相同，再比较第二个，以此类推。显然，此解法的时间复杂度为O(n^2)。经过测试，部分样例超出时间限制。
2.2 仔细想想
在大部分编程语言中，不仅数值型数据可以比较大小，字符串也可以比较大小。比较大小时，计算机会从前往后依次比较字符串各个字符ASCLL码值的大小，直至出现不等。那么，一个字符串数组中最大的与最小的字符串之间有什么关系呢？在示例1中，最大字符串为flower，最小字符串为flight，它们的最长公共前缀fl即为整个数组的最长公共前缀。这样的规律是普遍的。因此，我们可以先求出字符串数组的最大与最小的字符串，然后求出它们的最长公共前缀，，从而得到所求结果。此算法的时间复杂度只有O(n)。
3 求解代码
- c++代码
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
29class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
int num = strs.size();
//求字符串数组中最大与最小的字符串
string maxs = strs[0];
string mins = strs[0];
for(int i = 1; i < num; i++){
if(strs[i] > maxs){
maxs = strs[i];
}
if(strs[i] < mins){
mins = strs[i];
}
}
//求两字符串的最长公共前缀
string re = "";
int pos = 0;
while(pos < maxs.length() && pos < mins.length()){
if(maxs[pos] == mins[pos]){
re += maxs[pos];
pos++;
}else{
break;
}
}
return re;
}
}; - python代码
1
2
3
4
5
6
7
8class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
s1 = min(strs)
s2 = max(strs)
for i,x in enumerate(s1):
if x != s2[i]:
return s2[:i]
return s1
4 总结
找出规律，复杂度O(n^2)的算法可以化简到O(n)。