题目
Write a function to find the longest common prefix string amongst an array of strings.
- 大意： 写一个函数，找到一组字符串的公共最长前缀。
思路
我的：定义一个不断更新的变量，存储当前的最长前缀，循环时加以一定的优化，比如如果下一个字符串比当前的前缀还长，那么可以截断前缀后在进行比较。
参考的：这道题在discuss上看到了一些运用了python语法的解法，用到了zip,reduce,set等python特有的语法，顺便贴出。
代码
原创(Python):
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
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] <!--more--> com_str = list(strs[0]) for i in range(1, len(strs)): if len(strs[i]) < len(com_str): com_str = com_str[0:len(strs[i])] for j in range(len(com_str)): if com_str[j] != strs[i][j]: com_str = com_str[0:j] break |
Python(用了zip)
(《A pythonic solution, 52 ms》)
|
1 2 3 4 5 6 7 8 9 10 11 |
def longestCommonPrefix(self, strs): prefix = ''; # * is the unpacking operator, essential here for z in zip(*strs): bag = set(z); if len(bag) == 1: prefix += bag.pop(); else: break; return prefix; |
Python(用了reduce)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
class Solution: def lcp(self, str1, str2): i = 0 while (i < len(str1) and i < len(str2)): if str1[i] == str2[i]: i = i+1 else: break return str1[:i] def longestCommonPrefix(self, strs): if not strs: return '' else: return reduce(self.lcp,strs) |