題目描述
給定一組字符串，找出它們的最長公共前綴 (Longest Common Prefix)。如果沒有公共前綴，返回空字串 ""。
Input: strs = ["flower", "flow", "flight"]
Output: "fl"
- 這些字符串的公共前綴為
"fl"。
- 這些字符串的公共前綴為
範例 2：
Input: strs = ["dog", "racecar", "car"]
Output: ""
- 這些字符串之間沒有公共前綴，返回
""。
- 這些字符串之間沒有公共前綴，返回
解題思路
解決這個問題的關鍵在於如何高效地縮小範圍，找到最長公共前綴。以下列出常見的解法：
- 水平掃描法
將第一個字符串作為基準，依次與後面的字符串比較並縮小公共前綴的長度。 - 垂直掃描法
逐列掃描每個字符串，檢查每列的字符是否相同。如果發現不一致，立即結束。 - 分治法
將字符串數組分為兩部分，遞歸地找出每部分的最長公共前綴，然後合併。 - 二分查找法
以最短字符串的長度作為搜索範圍，使用二分查找法判斷某個長度是否為公共前綴。
解法 1：水平掃描法
思路
- 將第一個字符串作為初始公共前綴，依次與其他字符串比較並縮短公共前綴，直到匹配完成或前綴為空。
實現 (Python)
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
if not strs:
return ""
# 初始化 prefix 為第一個字符串
prefix = strs[0]
for s in strs[1:]:
# 縮短 prefix，直到找到公共部分
while not s.startswith(prefix):
prefix = prefix[:-1]
if not prefix:
return ""
return prefix
時間與空間複雜度
- 時間複雜度：O(S)，其中 S 是所有字符串字符的總數。最壞情況下，我們需要遍歷所有字符串的每個字符。
- 空間複雜度：O(1)，只需要額外的變量來存儲前綴。
解法 2：垂直掃描法
思路
- 逐列掃描每個字符串，檢查是否所有字符串在相同位置的字符一致。一旦發現某列字符不同，立即返回當前的公共前綴。
實現 (Python)
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
if not strs:
return ""
for i in range(len(strs[0])):
char = strs[0][i]
for s in strs[1:]:
# 如果超出長度或字符不匹配，結束掃描
if i >= len(s) or s[i] != char:
return strs[0][:i]
return strs[0]
時間與空間複雜度
- 時間複雜度：O(S)，同樣需要檢查所有字符。
- 空間複雜度：O(1)。
解法 3：分治法
思路
- 將字符串數組分成兩部分，遞歸地找出每部分的最長公共前綴，然後合併兩部分的結果。
實現 (Python)
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
if not strs:
return ""
def commonPrefix(left, right):
min_len = min(len(left), len(right))
for i in range(min_len):
if left[i] != right[i]:
return left[:i]
return left[:min_len]
def divideAndConquer(strs, l, r):
if l == r:
return strs[l]
mid = (l + r) // 2
left_prefix = divideAndConquer(strs, l, mid)
right_prefix = divideAndConquer(strs, mid + 1, r)
return commonPrefix(left_prefix, right_prefix)
return divideAndConquer(strs, 0, len(strs) - 1)
時間與空間複雜度
- 時間複雜度：O(S)，每次遞歸都需要比較兩部分的前綴。
- 空間複雜度：O(log(N))，其中 N 是字符串數組的大小，遞歸的深度最多為 log(N)。
解法 4：二分查找法
思路
- 將最短字符串的長度作為二分查找的搜索範圍。
- 每次檢查中間長度是否為公共前綴，並根據結果縮小範圍。
實現 (Python)
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
if not strs:
return ""
def isCommonPrefix(length):
prefix = strs[0][:length]
return all(s.startswith(prefix) for s in strs)
min_len = min(len(s) for s in strs)
low, high = 0, min_len
while low < high:
mid = (low + high + 1) // 2
if isCommonPrefix(mid):
low = mid
else:
high = mid - 1
return strs[0][:low]
時間與空間複雜度
- 時間複雜度：O(S × log(M))，其中 M 是最短字符串的長度，S 是所有字符串字符的總數。
- 空間複雜度：O(1)。
總結
最推薦的解法是水平掃描法或垂直掃描法，因為它們簡單直觀且能高效地處理大多數情況。如果數據規模較大，且字符串的長度有較大差異，可以考慮分治法或二分查找法進一步優化。
