3839. Number of Prefix Connected Groups

📘 題目敘述

給你一個字串陣列 words 和一個整數 k。

兩個位於不同索引的單字 a 和 b，如果 a[0..k-1] == b[0..k-1]，則它們是 prefix-connected。

一個 connected group 是一組單字，使得組內任意兩個單字都是 prefix-connected。

請回傳由給定字串形成的 connected group 中，包含至少兩個單字的 group 數量。

注意：

• 長度小於 k 的單字不能加入任何 group，必須忽略
• 重複字串視為不同單字
• 字串的 prefix 是從字串開頭開始的子字串，並且可以延伸到字串內任意位置

條件限制

• 1 <= words.length <= 5000
• 1 <= words[i].length <= 100
• 1 <= k <= 100
• words 中所有字串都只包含小寫英文字母

🧠 解題思路

題目要找的是：有多少個「前 k 個字母相同」的群組，且群組大小至少是 2。

所以我的想法是先把每個字的「長度為 k 的 prefix」抽出來，然後把這些 prefix 排序，讓相同的 prefix 全部擠在一起。

排序後我只要掃過一遍，就能看出每個 prefix 出現了幾次：

• 如果某個 prefix 出現至少 2 次，就代表有一個 connected group
• 題目說重複字串也算不同單字，所以同 prefix 的出現次數就是 group 的大小

我的寫法用 pre 記錄目前正在看的 prefix，用 first 來確保「同一個 prefix」只會被計數一次。

所有變數

• nword：把每個單字的前 k 個字母取出來後形成的新陣列（只收長度 >= k 的單字）
• count：答案，代表「至少兩個單字」的 prefix 群組數量
• pre：目前掃描到的 prefix 值，用來判斷是否換群組
• first：用來控制同一個 prefix 只計數一次（第一次遇到重複才加 1）

🪜 主要流程步驟

1. 把所有能用的單字轉成 k 長度的 prefix

我掃過 words，如果 s.size() >= k，就把 s.substr(0, k) 放進 nword。

2. 排序 nword，讓相同 prefix 排在一起

我做 sort(nword.begin(), nword.end())，排序後同一群 prefix 會連在一起。

3. 掃描排序後的 prefix，遇到某個 prefix 至少出現兩次就 count++

我用 pre 記錄目前群組、用 first 防止重複計數：每個 prefix 只在第一次重複時加一次。

⏱️ 複雜度

• 時間複雜度：O(m log m)
m 是長度 >= k 的單字數量。主要成本在排序。
• 空間複雜度：O(m)
nword 會存下所有 prefix。

💻 程式碼實作

class Solution {
public:
    int prefixConnected(vector<string>& words, int k) {
        vector<string> nword;
        for (string s : words) {
            if (s.size() >= k) {
                nword.push_back(s.substr(0, k));
            }
        }
        sort(nword.begin(), nword.end());
        int count = 0;
        string pre = "";
        bool first = true;
        for (string t : nword) {
            if (pre != t) {
                pre = t;
                first = true;
            } else if (pre == t && first) {
                first = false;
                count++;
            }
        }
        return count;
    }
};

🔗 題目連結

https://leetcode.com/problems/number-of-prefix-connected-groups/