最长公共前缀

问题描述

LeetCode14. 最长公共前缀

给你一个大小为 n 的字符串数组 strs ，其中包含n个字符串 , 编写一个函数来查找字符串数组中的最长公共前缀，返回这个公共前缀。

示例：

输入：["abca","abc","abca","abc","abcc"]

输出："abc"

分析问题

对于求一组字符串的公共前缀，我们可以先求出前两个字符串的公共前缀，然后拿该公共前缀再和第三个字符串求公共前缀，依次类推，知道遍历完所有字符串，即可得到该组字符串中的最长公共前缀。

更多图解高频算法，请关注公众号【程序员学长】，100多道高频算法题尽在这里，欢迎大家

我们来看一下代码的实现。

class Solution:
    def longestCommonPrefix(self, strs):
        #如果字符数组为空，则最长公共前缀为空，直接返回
        if not strs:
            return ""

        #首先令最长公共前缀max_prefix为字符数组strs的第一个字符串
        max_prefix=strs[0]
        n=len(strs)
        #依次和字符数组中的其它元素求最长公共前缀
        for i in range(1, n):
            max_prefix = self.lcp(max_prefix, strs[i])
            #如果遇到max_prefix为空，直接返回
            #因为空字符串和任意其它字符串的公共前缀都为空
            if not max_prefix:
                break

        return max_prefix

    def lcp(self, str1, str2):
        length, index = min(len(str1), len(str2)), 0
        #循环遍历，寻找最长公共前缀
        while index < length and str1[index] == str2[index]:
            index += 1
        return str1[:index]

除了横向遍历字符串数组外，即依次遍历数组中的每个字符串，然后更新最长公共前缀。我们还可以进行纵向遍历，即我们通过比较字符串数组中的每一列上的字符是否相同，如果相同则继续对下一列进行比较，如果不相同则表示当前列已经不再属于公共前缀了，直接返回当前列之前的部分就是最长公共前缀。

更多图解高频算法，请关注公众号【程序员学长】，100多道高频算法题尽在这里，欢迎大家

下面我们来看一下代码的实现。

class Solution:
    def longestCommonPrefix(self, strs):
        #如果字符数字为空，则最长公共前缀为空
        if not strs:
            return ""

        length=len(strs[0])
        n=len(strs)
        
        #比较所有字符串的每一列是否相同
        for i in range(length):
            c = strs[0][i]
            for j in range(1,n):
                if i>=len(strs[j]) or strs[j][i] != c:
                   return strs[0][:i]
                
        return strs[0]