Problem Description:
Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string “”.
题目链接
题目要求在给定的string List中找到它们最长的共同前缀。
思路一:
直接法,扫描第一个字符串,与此同时依次扫描其他字符串的同一位置,去判断是否是一样的字符,当遇到不一样的字母的时候就返回当前得到的前缀。
class Solution(object):
def longestCommonPrefix(self, strs):
"""
:type strs: List[str]
:rtype: str
"""
if not strs:
return ''
res = ''
for i in range(0,len(strs[0])):
for j in range(1, len(strs)):
if i >= len(strs[j]) or strs[j][i] != strs[0][i]:
return res
res = res + strs[0][i]
return res
结果如下:
?思路二:
对于字符串数组做一个排序,然后就只需要比较第一个和最后一个的公共前缀即可。
class Solution(object):
def longestCommonPrefix(self, strs):
"""
:type strs: List[str]
:rtype: str
"""
if not strs:
return ''
strs.sort()
res = ''
for i in range(0,len(strs[0])):
if i >= len(strs[-1]) or strs[0][i] != strs[-1][i]:
return res
res = res + strs[0][i]
return res
结果如下:
?Python的sort函数知识点:
sort()?函数用于对原列表进行排序,如果指定参数,则使用比较函数指定的比较函数。函数sort()会默认地按升序排列。
list.sort() 不会返回对象,但会改变原有的list。这点与sorted()不同,sorted()函数会返回一个列表,而sort()函数是直接在原来的基础上修改。
|