LeetCode - Longest Common Prefix（最長公共前綴）

題目描述

給定一個字符串數組 strs，找出所有字符串的 最長公共前綴。如果不存在公共前綴，則返回空字符串 ""。

範例：

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

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

解法思路

要找出字符串數組中所有字符串的最長公共前綴，有幾種方法可以解決該問題。最直觀且高效的方法是 橫向比較法。在橫向比較法中，我們逐步縮小前綴，直到找到最長的公共部分。

方法一：橫向比較

1. 初始化：將 prefix 設為數組中的第一個字符串。
2. 遍歷數組：
   • 從第二個字符串開始，逐一與 prefix 進行比較，找到兩者的公共前綴。
   • 每次比較後更新 prefix 為當前的公共前綴。
   • 如果 prefix 變成空字符串，則可以提前返回空字符串，因為沒有公共前綴。
3. 返回結果：當遍歷完成時，prefix 即為所有字符串的最長公共前綴。

方法二：縱向比較

1. 逐一比較每個字符串的第 i 個字符，如果所有字符串的第 i 個字符相同，則繼續下一個字符。
2. 當發現一個字符不同時，或者到達最短字符串的末尾時，即找到了最長公共前綴。

範例代碼

使用橫向比較法的實現如下：

def longestCommonPrefix(strs):
    if not strs:
        return ""
    
    prefix = strs[0]  # 將第一個字符串作為初始前綴
    for s in strs[1:]:  # 從第二個字符串開始
        while not s.startswith(prefix):  # 檢查當前字符串是否包含前綴
            prefix = prefix[:-1]  # 縮短前綴
            if not prefix:
                return ""  # 若前綴變為空，則返回空字符串
    
    return prefix

代碼解析

1. 初始化前綴：將第一個字符串設為初始前綴 prefix。
2. 比較每個字符串：
   • 使用 startswith() 函數檢查當前字符串是否包含 prefix。
   • 如果不包含，逐步減少 prefix 的長度。
3. 返回結果：當 prefix 剩下的部分無法再縮減時，則找到了最長公共前綴。

時間和空間複雜度

• 時間複雜度：O(S)，其中 S 是所有字符串中字符數的總和。在最壞情況下，prefix 會與每個字符串的字符進行比較。
• 空間複雜度：O(1)，因為只使用了固定的額外空間來存儲 prefix。