題目
編寫一個函數來查找字符串數組中的最長公共前綴。
如果不存在公共前綴，返回空字符串 “”。
示例
- 示例 1：
輸入：strs = ["flower","flow","flight"]
輸出："fl"
- 示例 2：
輸入：strs = ["dog","racecar","car"]
輸出：""
解釋：輸入不存在公共前綴。
提示
- 1 <= strs.length <= 200
- 0 <= strs[i].length <= 200
- strs[i] 僅由小寫英文字母組成
思路及算法代碼
思路
依次遍歷字符串數組中的每個字符串，對于每個遍歷到的字符串，更新最長公共前綴，當遍歷完所有的字符串以后，即可得到字符串數組中的最長公共前綴。
如果在尚未遍歷完所有的字符串時，最長公共前綴已經是空串，則最長公共前綴一定是空串，因此不需要繼續遍歷剩下的字符串，直接返回空串即可。
代碼
class Solution:def longestCommonPrefix(self, strs: List[str]) -> str:# 如果字符串列表為空，則沒有公共前綴if not strs:return ""# 初始化前綴為列表中的第一個字符串prefix, count = strs[0], len(strs)# 遍歷列表中的剩余字符串for i in range(1, count):# 更新前綴，找到當前前綴和當前字符串之間的最長公共前綴prefix = self.lcp(prefix, strs[i])# 如果沒有公共前綴，跳出循環if not prefix:breakreturn prefix# 輔助函數，找到兩個字符串之間的最長公共前綴def lcp(self, str1, str2):# 找到兩個字符串中長度較短的字符串的長度length, index = min(len(str1), len(str2)), 0# 遍歷字符串的字符，直到找到不匹配的字符或字符串結束while index < length and str1[index] == str2[index]:index += 1# 返回最長公共前綴return str1[:index]
復雜度分析
-
時間復雜度：O(mn)O(mn)O(mn)，其中 m 是字符串數組中的字符串的平均長度，n 是字符串的數量。最壞情況下，字符串數組中的每個字符串的每個字符都會被比較一次。
-
空間復雜度：O(1)。使用的額外空間復雜度為常數。
)
