本篇推文共計2000個字，閱讀時間約3分鐘。

01

題目描述

題目描述：

編寫一個函數(shù)來查找字符串?dāng)?shù)組中的最長公共前綴。

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

如下面的示例：

輸入：strs = ["flower","flow","flight"]
輸出："fl"

輸入：strs = ["dog","racecar","car"]
輸出：""
解釋：輸入不存在公共前綴。

提示：

1. 0<=strs.length<=200

2. 0<=strs[i].length<=200

3. strs[i]僅由小寫英文字母組成

02

方法和思路

我們注意題目中的條件，

此題可以先找出數(shù)組中字典序最小和最大的字符串，

最長公共前綴即為這兩個字符串的公共前綴。

可能這個時候你會問字典序是什么：

即比較當(dāng)前字符大小，

若當(dāng)前字符小則此字符串較小，
若相等則繼續(xù)往后比較，直到某一字符不相等或某一字符串比較結(jié)束，
比較結(jié)束都相等，則長度小的字符串較小。

在這里若輸入為

a, cd, abcd, 第一個字符分別是 a,c,a,

c字符大于a字符，所以此時第一輪比較中

則第二個字符串cd最大，

第二輪比較：

a已經(jīng)沒有了，abcd經(jīng)過剛才比較還剩bcd，

a,cd abcd排序的話，
cd最大，a最小，

公共前綴為"",
沒有相等的，為空。

我們用代碼表示此題的解法如下：

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:
            return ""
        str0=min(strs)
        str1=max(strs)
        for i in range(len(str0)):
            if str0[i]!=str1[i]:
                return str0[:i]
        return str0