编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀,返回空字符串 ""。 例如 输入:strs = ["flower","flaw","flight"] 输出:"fl"
思路
通过字符串比较的思路,以["flower","flaw","flight"]为例,三个字符串的第一个字符和第二个字符都是一样的,在比较第三个字符的时候,a<i<o,所以flaw最小,flower最大,flight排中间,而这里其实只要找最小和最大的公共前缀,因为最小和最大的公共前缀是相等的,那夹中间的必然也相等!否则他就不是排中间了!
涉及知识点:切片、字符串比较、内建函数min、max
class Solution: def longestCommonPrefix(self, strs): if not strs: return "" min_s = min(strs) max_s = max(strs) for i, num in enumerate(list(min_s)): if num != max_s[i]: return max_s[:i] return min_s
时间复杂度:O(n) 执行用时:32 ms 内存消耗:15.1 MB
思路
通过zip函数把["flower","flaw","flight"]对象中的元素打包成一个个元组
然后使用map+set去重,得到的列表中元素长度为1的就是公共的,把他们加起来就拿到了最长公共前缀
class Solution: def longestCommonPrefix(self,strs): if strs == "": return "" s = list(map(set, zip(*strs))) # s是[{'f'}, {'l'}, {'i', 'a', 'o'}, {'w', 'g'}] result = "" for i,num in enumerate(s): num = list(num) if len(num) > 1: break result += num[0] return result
时间复杂度:O(n) 执行用时:32 内存消耗:15
zip在python3中返回的是一个对象,需要使用list()来转换成列表