【一天一道Leetcode】最长公共前缀
看那个码农
共 1612字,需浏览 4分钟
· 2021-03-26
本篇推文共计2000个字,阅读时间约3分钟。
01
题目描述
题目描述:
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀,返回空字符串""。
如下面的示例:
输入: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最小,
公共前缀为"",
没有相等的,为空。
![](https://filescdn.proginn.com/186d135fbdb47efc6550ad1a7b6f2f2f/7d2bd0fad5c3ba933f1d870d5e85801e.webp)
我们用代码表示此题的解法如下:
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
![](https://filescdn.proginn.com/edb4a4847439aa611957c71d5f6378a7/0c4f3036ded8244fe65ca692a3b83521.webp)
【年终总结】你好2021,再见2020。
![](https://filescdn.proginn.com/e5b0d9bcdd782cd82578b69b53fb402a/c60cfaebbfda26ae628744d01f4fd533.webp)
【快速写好毕业论文】你不得不知晓的七个常用文献搜索平台
![](https://filescdn.proginn.com/e739fdb5f32bde7eb773b616ecd43b80/a1d9222e1715f8c8f9c4702105a44318.webp)
【秋招纪实录】一篇特别正经的【腾讯】求职经验分享
![](https://filescdn.proginn.com/90836ce339628a188f2c623b635c0f59/10e218f629c2802c1b344caa0e3e80ae.webp)
【一天一道Leetcode】回文字符串-最少分割次数
![](https://filescdn.proginn.com/8151da11a43d1a81853e127cd8f6bf1a/b6da8d19f486508a575e69ef8759d74b.webp)
【一天一道Leetcode】整数反转
![](https://filescdn.proginn.com/79c7bba1fc7f014f9a4b27839a6c4eee/b7d738157041b5816086154523d8e859.webp)
【一天一道Leetcode】套信封问题
你与世界
只差一个
公众号
评论