题解 | #最长公共前缀#

#
#
# @param strs string字符串一维数组
# @return string字符串
# 这部分代码是在纵向比较的基础上对于非等长等特殊情况做优化，提升处理速度
class Solution:
    def longestCommonPrefix(self , strs ):
        # write code here
        sameChar = ""
        if len(strs) == 0:
            return sameChar                            #特殊情况返回空
        if len(strs) == 1:
            return strs[0]                             #只有一个的情况直接返回其本身
        maxLen = len(strs[0])
        minLen = len(strs[0])
        maxStrs = 0                                    #由于后续有判断，所以此处初始最小值定为0，
        minStrs = 0                                    #若不定，在遇到minLen或maxLen始终不满足条件时，后续无此值报错
        for i in range(len(strs)):                     #此处一次for循环同时找出最长和最短串
            if len(strs[i]) > maxLen:
                maxLen = len(strs[i])
                maxStrs = i
            if len(strs[i]) <= minLen:
                minLen = len(strs[i])
                minStrs = i
        if minLen == maxLen:                           #原题测试用例不足，如果全部等长的时候，又恰好取到的两个不同的串的长度一致时，会返回错误结果，如["abca","abcc","abce","abcf","abca"]时，会返回"abca"而非"abc"
            for j in range(len(strs[0])):
                for i in range(1,len(strs)):
                    if strs[0][j] == strs[i][j]:
                        if i >= len(strs)-1:
                            sameChar += strs[0][j]
                    else:
                        break
            return sameChar                            #此部分代码不加仍可以通过题目的样例测试
        for i in range(len(strs[minStrs])):            #此处一次for循环完成要求，找出最长公共前缀
            if strs[minStrs][i] == strs[maxStrs][i]:
                sameChar += strs[minStrs][i]
            else:
                break
        return sameChar

将情况拆开讨论，牺牲一定的空间复杂度换取时间复杂度的降低，通过分情况讨论来加速程序运行，本质核心代码还是纵向比较，只是将非等长的情况下抽离出来看，优化非等长时的比较次数