[LeetCode解題攻略] 14. Longest Common Prefix

題目描述

給定一組字符串，找出它們的最長公共前綴 (Longest Common Prefix)。如果沒有公共前綴，返回空字串 ""。

範例 1：

Input: strs = ["flower", "flow", "flight"]
Output: "fl"

1. • 這些字符串的公共前綴為 "fl"。

範例 2：

Input: strs = ["dog", "racecar", "car"]
Output: ""

1. • 這些字符串之間沒有公共前綴，返回 ""。

解題思路

解決這個問題的關鍵在於如何高效地縮小範圍，找到最長公共前綴。以下列出常見的解法：

1. 水平掃描法
   將第一個字符串作為基準，依次與後面的字符串比較並縮小公共前綴的長度。
2. 垂直掃描法
   逐列掃描每個字符串，檢查每列的字符是否相同。如果發現不一致，立即結束。
3. 分治法
   將字符串數組分為兩部分，遞歸地找出每部分的最長公共前綴，然後合併。
4. 二分查找法
   以最短字符串的長度作為搜索範圍，使用二分查找法判斷某個長度是否為公共前綴。

解法 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)。

總結

最推薦的解法是水平掃描法或垂直掃描法，因為它們簡單直觀且能高效地處理大多數情況。如果數據規模較大，且字符串的長度有較大差異，可以考慮分治法或二分查找法進一步優化。