Leetcode-Easy-14. Longest Common Prefix(python)

题目

image.png

思路

给定一个包含多个字符串的列表，找到这个列表中所有元素的最长前缀。
有一个相对简单的办法，先遍历列表，统计最短元素的长度，即为最大公共前缀的长度上限为L;同时把长度为L的字符串Elem记录下来，如果最长前缀有L位，那最长前缀必然为Elem.
接下来，遍历每个字符串的前L位元素，判断是否每一位都与Elem相同，相同则记录在A里，遇到不同或者遍历结束后，输出的A即为最长前缀
时间复杂度： O(n)+O(L)O(n) = O(nn)

代码实现

class Solution:
    def longgestCommonPrefix(self,strs):
        if len(strs)<1 or len(strs)>200:
            return None
        #先获取列表最短字符串长度，即为最大公共前缀的长度上限;同时获取此长度中排最靠前的字符串记录下来
        lenth = 100000000000
        for elem in strs:
            if len(elem)< lenth:
                lenth = len(elem)
                a = elem
        common_prefix = ""

        for i in range(lenth):  #遍历每个字符串的前lenth位元素，判断是否每一位都与a相同
            for s in strs:
                if s[i] != a[i]:
                    return common_prefix
            common_prefix = common_prefix + a[i]
        return common_prefix