【一天一道Leetcode】最长公共前缀
题目描述
题目描述：
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串""。
如下面的示例：
输入：strs = ["flower","flow","flight"]
输出："fl"
输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。提示：
1. 0<=strs.length<=200
2. 0<=strs[i].length<=200
3. strs[i]仅由小写英文字母组成
02
方法和思路
我们注意题目中的条件，
此题可以先找出数组中字典序最小和最大的字符串，
最长公共前缀即为这两个字符串的公共前缀。
可能这个时候你会问字典序是什么：
即比较当前字符大小，
若当前字符小则此字符串较小，
若相等则继续往后比较，直到某一字符不相等或某一字符串比较结束，
比较结束都相等，则长度小的字符串较小。在这里若输入为
a, cd, abcd, 第一个字符分别是 a,c,a,
c字符大于a字符，所以此时第一轮比较中
则第二个字符串cd最大，
第二轮比较：
a已经没有了，abcd经过刚才比较还剩bcd，
a,cd abcd排序的话，
cd最大，a最小，
公共前缀为"",
没有相等的，为空。
我们用代码表示此题的解法如下：
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
if not strs:
return ""
str0=min(strs)
str1=max(strs)
for i in range(len(str0)):
if str0[i]!=str1[i]:
return str0[:i]
return str0本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2021-03-25，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录