Leetcode 最长公共前缀
Leetcode 最长公共前缀
Categories:
最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 “"。
示例 1:
输入: ["flower","flow","flight"]
输出: "fl"
示例 2:
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
说明:
所有输入只包含小写字母 a-z 。
解题思路
原始数组转为set,再转为list, 去重
如果只有一个元素, 最长公共前缀就是该元素
设置初始最长公共前缀为”"
对数组各元素同步截取前n个字符. 放入set去重, 如果set长度为1, 则公共前缀为集合的元素
继续对各元素同步截取, 直到set长度不为1, 返回保存的公共前缀
Answer
1#
2# @lc app=leetcode.cn id=14 lang=python3
3#
4# [14] 最长公共前缀
5#
6
7# @lc code=start
8class Solution:
9 def longestCommonPrefix(self, strs: List[str]) -> str:
10 strs = list(set(strs))
11 if len(strs) == 1:
12 return strs[0]
13 idx = 1
14 prefix = ""
15 while True:
16 ary = [i[0:idx] for i in strs]
17 if len(set(ary))==1:
18 prefix = ary[0]
19 idx = idx + 1
20 else:
21 break
22 return prefix
23
24# @lc code=end
Accepted
118/118 cases passed (40 ms)
Your runtime beats 80.45 % of python3 submissions
Your memory usage beats 6.15 % of python3 submissions (13.7 MB)