LeetCode 刷题记录14. 最长公共前缀

题目描述：

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 “”。

说明：
示例 1：

输入：strs = [“flower”,“flow”,“flight”]
输出：“fl”
示例 2：

输入：strs = [“dog”,“racecar”,“car”]
输出：“”
解释：输入不存在公共前缀。

提示：

1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] 仅由小写英文字母组成

解答：

Python3版本：

解法一：横向比较法

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        # 横向比较法-两两比较
        if not strs:
            return ""        
        result, str_count = strs[0], len(strs)
        for i in range(1, str_count):
            result = self.lcp(result, strs[i])
            if not result:
                break
            return result
    def lcp(self, s1, s2):
        min_length, index = min(len(s1), len(s2)), 0
        while ((index < min_length) and (s1[index] == s2[index])):
            index += 1
        return s1[:index]

                

解法二：纵向比较法

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        # 纵向比较法
        if not strs:
            return ""
        length, strs_count = len(strs[0]), len(strs)
        # 遍历第一个字符串
        for i in range(length):
            # 依次比较第一个字符串中的字符
            temp = strs[0][i]
            if any(i==len(strs[j]) or temp!=strs[j][i] for j in range(1, strs_count)):
                return strs[0][:i]
        return strs[0]