**Leetcode 14 Longest Common Prefix

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

这道题涉及的知识点有点多，慢慢总结。