14. 最长公共前缀
点击上方,跳转至Leetcode
题目描述
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀,返回空字符串 ""
。
示例 1:
输入:strs = ["flower","flow","flight"] 输出:"fl"
示例 2:
输入:strs = ["dog","racecar","car"] 输出:"" 解释:输入不存在公共前缀。
提示:
1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i]
仅由小写英文字母组成
解法一
横向扫描:写一个longestCommonPrefix方法,用于返回两个字符串的公共前缀
然后再主方法中,先让第一个字符串定为公共前缀,然后依次和后面的字符串执行longestCommonPrefix方法,更新公共前缀,最后公共前缀越来越短。
复杂度分析:
时间复杂度:\(O(mn)\),其中 m 是字符串数组中的字符串的平均长度,n 是字符串的数量。最坏情况下,字符串数组中的每个字符串的每个字符都会被比较一次。
空间复杂度:\(O(1)\)。使用的额外空间复杂度为常数。
Python3
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
if not strs:
return ""
prefix,count = strs[0],len(strs)
for i in range(1,count):
prefix = self.lcp(prefix,strs[i])
if not prefix:
break
return prefix
def lcp(self,str1,str2):
length ,index = min(len(str1),len(str2)),0
while index <length and str1[index] == str2[index]:
index += 1
return str1[:index]
C++
class Solution {
public:
string longestCommonPrefix(vector<string>& strs){
if(!strs.size())
return "";
string prefix = strs[0];
int count = strs.size();
for(int i=1;i<count; ++i){
prefix = longestCommonPrefix(prefix,strs[i]);
if(!prefix.size())
break;
}
return prefix;
}
string longestCommonPrefix(const string &str1,const string &str2){
int length = min(str1.size(),str2.size());
int index = 0;
while(index < length && str1[index] == str2[index])
++index;
return str1.substr(0,index);
}
};
解法二
纵向扫描:依次遍历每个字符串,更新最长公共前缀。另一种方法是纵向扫描。纵向扫描时,从前往后遍历所有字符串的每一列,比较相同列上的字符是否相同,如果相同则继续对下一列进行比较,如果不相同则当前列不再属于公共前缀,当前列之前的部分为最长公共前缀。
复杂度分析:
时间复杂度:\(O(mn)\),其中 m 是字符串数组中的字符串的平均长度,n 是字符串的数量。最坏情况下,字符串数组中的每个字符串的每个字符都会被比较一次。
空间复杂度:\(O(1)\)。使用的额外空间复杂度为常数。
Python3
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
if not strs:
return ""
length,count = len(strs[0]),len(strs)
for i in range(length):
c= strs[0][i]
for j in range(1,count):
if(i==len(strs[j]) or strs[j][i] !=c):
return strs[0][:i]
return strs[0]
C++
class Solution2 {
public:
string longestCommonPrefix(vector<string>& strs){
if(!strs.size())
return "";
int length = strs[0].size();
int count = strs.size();
for(int i=0;i<length;++i){
char c = strs[0][i];
for(int j=1;j<count;++j){
if(i==strs[j].size() || strs[j][i] !=c){
return strs[0].substr(0,i);
}
}
}
return strs[0];
}
};
标签:0014,return,前缀,strs,复杂度,公共,字符串,Leetcode
From: https://www.cnblogs.com/yege/p/17496289.html