该解法执行时间 40ms
思路:
过滤掉无值和只有一个值的情况
取出列表中最短的字符串(如果有最长公共前缀,最多也就是其中最短的一个值)
遍历列表,判断每一个字符串在从开头截取出来的同等长度下是否一样,一样的话,计数加1;不一样直接跳过
判断本次循环结束最终的计数是否与列表长度一致,一致,说明这就是最长公共前缀
不一致,将当前最短值截取掉最后一位,加上死循环,再次进行判断
如果没有公共前缀,在最短值切成空字符串时,判断相等,循环结束
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time : 2019/11/11 19:50
# @Author : QYF
# @File : 14_最长公共前缀.py
"""
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀,返回空字符串 ""。
示例 1:
输入: ["flower","flow","flight"]
输出: "fl"
示例 2:
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
说明:
所有输入只包含小写字母 a-z 。
"""
from typing import List
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
# 我的解法 有点长,不过还好,执行时间 40ms
if len(strs) == 0:
return ""
if len(strs) == 1:
return strs[0]
# 取出列表中最短的值
s_min = min(strs, key=len)
while 1:
t_num = 0 # 能对上的数量
for i in range(len(strs)):
if s_min == strs[i][:len(s_min)]:
t_num += 1
if t_num == len(strs):
return s_min
s_min = s_min[:-1]
return ""
# 大佬的解法
# if not strs:
# return ""
# res = strs[0]
# i = 1
# while i < len(strs):
# while strs[i].find(res) != 0:
# res = res[0:len(res)-1]
# i += 1
# return res
if __name__ == '__main__':
a = ["flower", "asdf", "xcvbdgh"]
# a = []
res = Solution().longestCommonPrefix(a)
print(res)
