题目描述

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

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

示例 1:

输入: ["flower","flow","flight"]
输出: "fl"

示例 2:

输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。

说明:

所有输入只包含小写字母 a-z 。

解题思路

1. 穷举法

   这种方法是最容易理解的一种方法。首先获取到列表中长度最小的字符串暂定作为最长的匹配前缀，然后用这个前缀依次和列表里的字符串判断是否包含这个前缀。发现不是前缀的时候，暂定前缀就缩短一个字符。如此反复进行比较，直到前缀字符串变为空串。当然这个方法的时间复杂度是很高的O(m*n)。

穷举法实现

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:
            return ''
        strs.sort(key=lambda i:len(i))
        reg=strs[0]
        for i, c in enumerate(reg):
            for j in strs:
                if c != j[i]:
                    return reg[:i]
        return reg

2. ASCII排值法

   利用python的max()和min()，在Python里字符串是可以比较的，按照ascII值排，举例abb， aba，abac，最大为abb，最小为aba。所以只需要比较最大最小的公共前缀就是整个数组的公共前缀。

排值法实现

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs: return ""
        s1 = min(strs)
        s2 = max(strs)
        for i,x in enumerate(s1):
            if x != s2[i]:
                return s2[:i]
        return s1