本文原地址在我的博客：Leetcode 第14題 最長公共前綴
題目地址??：https://leetcode.cn/problems/longest-common-prefix/
0x01 題目內容
編寫一個函數(shù)來查找字符串數(shù)組中的最長公共前綴义屏。
如果不存在公共前綴腕唧，返回空字符串 ""半醉。
示例 1：
輸入：strs = ["flower","flow","flight"]
輸出："fl"
示例 2：輸入：strs = ["dog","racecar","car"]
輸出：""
解釋：輸入不存在公共前綴福也。提示：
1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] 僅由小寫英文字母組成
0x02 算法思路
同學教的一個非常妙的解法：
0x001 算法原理
<img src="https://cdn.jsdelivr.net/gh/hetaozdh/hetaozdh.github.io@pic/img/image-20220726114529799.png" alt="ASCII表格 來自維基百科" style="zoom: 50%;" />
Python中字符串是可以比較大小的，比較的規(guī)則是根據(jù)ASCII表來將字符串轉換成數(shù)組再按位比較涎显，舉幾個例子：
abc和bac比較
有"abc"<"bac"
原因是通過查表，a、b藏否、c的數(shù)字編號分別為97、98充包、99副签。
abc -> [97, 98, 99]
bac -> [98, 97, 99]
從第一位開始比較，因為97 < 98基矮，直接得到"abc"<"bac"而不需要處理后面的部分
abc和aac進行比較
有"abc">"aac"
abc -> [97, 98, 99]
aac -> [97, 97, 99]
從第一位開始比較淆储，有97 = 97，所以接著吧比較第二位家浇，很明顯有98 > 97本砰，得出"abc">"aac"
abcc和abc進行比較
有"abcc">"abc"
abcc -> [97, 98, 99, 99]
abc -> [97, 98 ,99]
這次我們發(fā)現(xiàn)，對比前三位都一樣的情況下钢悲，字符串a(chǎn)bc沒有第四位和abcc進行比較了点额。這時候就給abc的結尾補上空字符：
abc -> ['a', 'b', 'c', NUL] -> [97, 98, 99, 0]
空字符NUL對應編號為0，是ASCII表中最小的莺琳。
自然就有"abcc">"abc"
0x002 利用思路
通過比對字符串咖楣，可以把一個list[str]（全是字符串的列表）進行排序，從而可以得到一個最大值和最小值芦昔。
max_str: str = max(strs)
min_str: str = min(strs)
應該有诱贿，在strs: list[str]中，max_str和min_str是“差得最遠”的（或區(qū)別最大的）咕缎。二者的最長公共前綴（具有相似特征）應該也是strs中每一項的最長公共前綴珠十。
使用縱向掃描求max_str和min_str的最長公共前綴。
即設變量lcp: str凭豪。下標從0開始掃描兩個字符串焙蹭，若相同則將該位字符加入lcp尾部，若不同則跳出循環(huán)嫂伞，返回lcp孔厉。
0x03 算法實現(xiàn)
Python代碼
# 最長公共前綴
# 14 longest-common-prefix
# Code By 吃核桃不吐核桃殼
# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
@staticmethod
def longestCommonPrefix(strs: list[str]) -> str:
lcp: str = ''
max_str: str = max(strs)
min_str: str = min(strs)
len_str: int = min(len(max_str), len(min_str))
for num in range(len_str):
if max_str[num] == min_str[num]:
lcp += max_str[num]
else:
break
return lcp
# leetcode submit region end(Prohibit modification and deletion)
順便說下python3.6之后支持了類型注解，代碼寫出來規(guī)范而且很漂亮帖努，有效增加了可讀性撰豺。
使用typing庫還可以自定義數(shù)據(jù)類型和數(shù)據(jù)類型別名。
