14. Longest Common Prefix

📘 題目敘述

請你寫一個函式，用來找出一個字串陣列中，最長的共同前綴字串。

如果不存在共同前綴，則回傳空字串 ""。

條件限制

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i] 只由小寫英文字母組成

🧠 解題思路

我把這題想成一個很直接的檢查流程：

我先決定「最多能比到幾個字」，因為共同前綴不可能比最短字串還長。 所以我先掃一次整個陣列，找到最短字串長度 mins。

接著我用 j 從左到右一個字一個字比：

• 先拿第一個字串在位置 j 的字元當作目標字 goal
• 再把所有字串在同一個位置 j 的字元都拿來跟 goal 比
• 只要有任何一個字串在這個位置不同，代表共同前綴到這裡就結束，直接回傳目前累積的 ans

如果這一輪全部都相同，代表第 j 個字元屬於共同前綴，把它加進 ans，然後繼續下一個位置。

所有變數

• mins：所有字串中最短的長度，用來限制最多能比到哪個位置
• n：字串陣列 strs 的大小
• ans：目前累積出的共同前綴字串
• goal：用第一個字串在第 j 個位置的字元當作「本輪要比對的目標字元」

🪜 主要流程步驟

1. 先找出最短字串長度 mins

我先把 mins 設成很大，然後掃過所有字串，用 mins = min(mins, strs[i].size()) 找出最短長度。 因為共同前綴最多只能到這個長度，超過一定不可能。

2. 逐字元位置 j 從 0 比到 mins-1

對每個位置 j：

先拿 strs[0][j] 當作 goal，代表「這一輪大家應該都要長得跟它一樣」。

3. 檢查所有字串在位置 j 是否都等於 goal

我用 k 掃過所有字串：

• 只要出現 strs[k][j] != goal
  • 代表共同前綴到這裡停止
  • 直接回傳目前的 ans

4. 若全部相同，把 goal 加進 ans

如果這一輪沒有任何不一樣，代表這個位置確實屬於共同前綴，做 ans += goal，繼續比下一個位置。

5. 全部比完仍沒中斷，就回傳 ans

如果一路比到 mins 都沒有不同，代表最短字串整段都是共同前綴，回傳 ans。

⏱️ 複雜度

• 時間複雜度：O(n * m) m 是最短字串長度。外層最多跑 m 次，每次內層比 n 個字串。
• 空間複雜度：O(1)（不含回傳字串） 只用到幾個變數；ans 是輸出本身。

💻 程式碼實作

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        int mins = INT_MAX;
        int n = strs.size();
        string ans = "";
        for (int i = 0; i < n; i++) {
            mins = min(mins, (int)strs[i].size());
        }
        for (int j = 0; j < mins; j++) {
            char goal = strs[0][j];
            for (int k = 0; k < n; k++) {
                if (goal != strs[k][j]) {
                    return ans;
                }
            }
            ans += goal;
        }
        return ans;
    }
};

🔗 題目連結

https://leetcode.com/problems/longest-common-prefix/