上一篇:算法隨筆_45: 車隊-CSDN博客

=====

題目描述如下:

編寫一個函數來查找字符串數組中的最長公共前綴。

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

示例 1：

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

=====

算法思路:

根據題目描述，如果strs[0]和strs[1]的公共前綴為字符串pre0，那么strs[0]到strs[2]這三個字符串的公共前綴只能是pre0和strs[2]的公共前綴pre1。

strs[0]到strs[3]這4個字符串的公共前綴只能是pre1和strs[3]的公共前綴pre2。

以此類推，我們可以依據此規則寫出這道題的代碼如下:

class Solution(object):def longestCommonPrefix(self, strs):""":type strs: List[str]:rtype: str"""strs_len=len(strs)pre=strs[0]for i in range(1,strs_len):s=strs[i]len_min=min(len(pre),len(s))cnt=0for j in range(len_min):if pre[j]==s[j]:cnt+=1else:breakpre=s[:cnt]return pre