一、题目描述
编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀,返回空字符串 ""
示例:
输入: ["flower","flow","flight"]
输出: "fl"
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
二、代码实现
方法一:比较多个字符串的最长公共前缀,实际上只需要比较最大和最小的,只要最大和最小有共同前缀,其他中间都有。这里的最大最小是把字符串中每个字符的ASCII码相加,分别找出最大和最小。
class Solution(object):
def longestCommonPrefix(self, strs):
"""
:type strs: List[str]
:rtype: str
"""
if len(strs) == 0: return ""
if len(strs) == 1: return strs[0]
minstr = min(strs)
maxstr = max(strs)
commonstr = ""
strlen = min(len(minstr), len(maxstr))
for idx in range(strlen):
if minstr[idx] == maxstr[idx]:
commonstr = commonstr + minstr[idx]
else:
break
return commonstr
方法二:使用os.path.commonprefix
class Solution(object):
def longestCommonPrefix(self, strs):
"""
:type strs: List[str]
:rtype: str
"""
return os.path.commonprefix(strs)
方法三:使用zip,将字符串拆分成字符,逐个比较
class Solution(object):
def longestCommonPrefix(self, strs):
"""
:type strs: List[str]
:rtype: str
"""
commonpath = ""
for chars in zip(*strs):
if len(set(chars)) == 1:
commonpath = commonpath + chars[0]
else:
break
return commonpath
网友评论