Write a function to find the longest common prefix string amongst an array of strings.
思路:
- 找出所有字符串共同的前缀。以第一个字符串为标的,依次进行比较。
- 设置共同前缀的index为0,最小长度是所有字符串长度中最小的那个。依次比较strs中的元素,如果不等,就返回第一个字符串到index长度的slice。index加一,直至大于最小长度。
#!/usr/bin/env python
# -*- coding: UTF-8 -*-
class Solution(object):
def longestCommonPrefix(self, strs):
"""
:type strs: List[str]
:rtype: str
"""
if len(strs) == 0:
return ""
longest = len(strs[0])
for e in strs[1:]:
index = 0
while index < len(e) and index < longest and strs[0][index] == e[index]:
index += 1
longest = min(index, longest)
return strs[0][:longest]
def longestCommonPrefix2(self, strs):
if len(strs) <= 1:
return strs[0] if len(strs)==1 else ""
end, minlength = 0, min([len(s) for s in strs])
while (end < minlength):
for i in xrange(1, len(strs)):
if strs[i][end] != strs[i-1][end]:
return strs[0][:end]
end += 1
return strs[0][:end]
if __name__ == '__main__':
sol = Solution()
strs = ["abcd", "abcde", "abcdef"]
strs = ["a", "b"]
print sol.longestCommonPrefix(strs)
print sol.longestCommonPrefix2(strs)