題目描述

編寫(xiě)一個(gè)函數(shù)來(lái)查找字符串?dāng)?shù)組中的最長(zhǎng)公共前綴。

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

示例 1:

輸入: ["flower","flow","flight"]

輸出: "fl"

示例 2:

輸入: ["dog","racecar","car"]

輸出: ""

解釋: 輸入不存在公共前綴。

考點(diǎn)

根據(jù)列表中的字符串長(zhǎng)度排序

兩層for循環(huán)的使用，for|else的使用

算法1

從下標(biāo)0開(kāi)始，判斷每一個(gè)字符串同一索引所對(duì)應(yīng)的值，判斷是否全部相同。直到遇到不全部相同的時(shí)候return。

由于提供的單詞長(zhǎng)度不同，應(yīng)該以最小單詞為基準(zhǔn)進(jìn)行比較，如["flower","flow","flight"]中應(yīng)該以flow來(lái)和剩下的單詞一一對(duì)比。

所有單詞同一索引所對(duì)應(yīng)的值相等，則更新最長(zhǎng)公共前綴

有一個(gè)單詞與其他單詞同一索引所對(duì)應(yīng)的值不相等，則返回最后更新的最長(zhǎng)公共前綴

代碼1

def longestCommonPrefix(strs):""":type strs: List[str]:rtype: str"""strs.sort(key =len)# 根據(jù)列表中的字符串長(zhǎng)度排序if not strs:return ''result = ''#記錄公共前綴for i in range(len(strs[0])):#以列表中長(zhǎng)度最小的單詞為基準(zhǔn)進(jìn)行遍歷for j in strs:#遍歷列表中的每個(gè)字符串if j[i] != strs[0][i]:#如果列表中的字符串的對(duì)應(yīng)下標(biāo)是否相同return resultelse:result += strs[0][i]#如果所有字符串下標(biāo)都相同，更新最長(zhǎng)公共前綴return result print(longestCommonPrefix([""]))

算法2

利用python的max()和min()，在Python里字符串是可以比較的，按照ascII值排，舉例abb，aba，abac，最大為abb，最小為aba。所以只需要比較最大最小的公共前綴就是整個(gè)數(shù)組的公共前綴

代碼2

def longestCommonPrefix(self, strs):""":type strs: List[str]:rtype: str"""s1 = min(strs)s2 = max(strs)for i,x in enumerate(s1):if x != s2[i]:return s2[:i]return s1

?

轉(zhuǎn)載于:https://www.cnblogs.com/hyj691001/p/10799710.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的20190501-编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串...的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。