Leetcode 14 Longest Common Prefix"/>
**Leetcode 14 Longest Common Prefix
Leetcode 14 Longest Common Prefix
题目描述
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 “”.
Example 1:
Input: ["flower","flow","flight"]
Output: "fl"
Example 2:
Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.Note:
All given inputs are in lowercase letters a-z.
来源:力扣(LeetCode)
链接:
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路解析
- 思路一
水平扫描法,首先找到列表中第一个元素和第二个元素的最长公共前缀,再找得到的前缀与第三个元素的最长公共前缀,这样不断重复,直到遍历完整个列表,或者得到为空的最长公共前缀。
代码如下:
class Solution:def longestCommonPrefix(self, strs: List[str]) -> str:if strs is None or strs == []:return ""common = strs[0]length = len(strs)i = 0for i in range(0, length):while strs[i].find(common) != 0:common = common[:-1]i += 1return common
其时间复杂度在最坏的情况下为 O ( S ) , S 为 列 表 中 所 有 字 符 的 数 量 之 和 O(S),S为列表中所有字符的数量之和 O(S),S为列表中所有字符的数量之和(如果列表中的元素均相同,那么每一个元素的每一个字符都会进行比较,所以时间复杂度为 O ( S ) O(S) O(S))
- 思路二
这道题也能以分治的思想来做,类似于二分查找,只不过二分查找是寻找某元素是否在集合中,而这道题是求最长公共子串。
将列表一分为二,寻找两个子列表的最长公共子串,而要求两个子列表的最长公共子串,也需要将两个子列表一分为二,重复操作。即我们将一个大问题不断分解,成若干个相同的能够直接求解的子问题,能用相同的方法独立求解,且子问题的解共同构成了我们大问题的解。
代码如下:
class Solution:def longestCommonPrefix(self, strs: List[str]) -> str:if strs is None or strs == []:return ""return self.subLongestCommonPrefix(strs, 0, len(strs) - 1)def subLongestCommonPrefix(self, strs, left, right):if left == right:return strs[left]mid = (left + right) // 2lcp_left = self.subLongestCommonPrefix(strs, left, mid)lcp_right = self.subLongestCommonPrefix(strs, mid + 1, right)return self.commonPrefix(lcp_left, lcp_right)def commonPrefix(self, sub1, sub2):length = len(min(sub1, sub2, key=len))i = 0for i in range(0, length):if sub1[i] != sub2[i]:return sub1[:i]return sub1[:i]
- 思路三
首先,从列表中选取出长度最小的字符串,如果所有字符串有最长公共前缀的话,也肯定是该字符串的前缀。我们可以先选取出该字符串的首元素,判断它是不是列表中所有字符串的公共前缀,如果是的话,我们选取该字符串的前两个字符,判断它是不是列表中所有字符串的公共前缀,如果不是的话,返回已得到的前缀部分。如此重复,直到遍历完该字符串或返回前缀部分。
这一遍历过程,我们可以利用二分查找的思路来提高效率,利用二分查找来得到最大公共子串的长度,进而利用长度区间截取出最长公共前缀,得到结果。
class Solution:def longestCommonPrefix(self, strs: List[str]) -> str:if strs is None or strs == []:return ""minLen = len(min(strs, key=len))left = 1right = minLenwhile left <= right:mid = (left + right) // 2if self.isCommonPrefix(strs, mid):left += 1else:right -= 1return strs[0][:(left + right) // 2]def isCommonPrefix(self, strs, mid):common = strs[0][:mid]i = 0length = len(strs)for i in range(0, length):if strs[i].find(common) != 0:return Falsei += 1return True
- python大法好啊,膜大佬
class Solution:def longestCommonPrefix(self, strs: List[str]) -> str:if strs is None or strs == []:return ""s = list(map(set, zip(*strs)))common = ""for i, v in enumerate(s):v = list(v)if len(v) > 1:breakcommon += v[0]return common
class Solution:def longestCommonPrefix(self, strs: List[str]) -> str:if strs is None or strs == []:return ""s1 = min(strs)s2 = max(strs)for i, v in enumerate(s1):if v != s2[i]:return s2[:i]return s1
这道题涉及的知识点有点多,慢慢总结。
更多推荐
**Leetcode 14 Longest Common Prefix
发布评论