📘 題目敘述
給你一個字串陣列 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 <= 50001 <= words[i].length <= 1001 <= k <= 100words中所有字串都只包含小寫英文字母
🧠 解題思路
題目要找的是：有多少個「前 k 個字母相同」的群組，且群組大小至少是 2。
所以我的想法是先把每個字的「長度為 k 的 prefix」抽出來，然後把這些 prefix 排序，讓相同的 prefix 全部擠在一起。
排序後我只要掃過一遍，就能看出每個 prefix 出現了幾次：
- 如果某個 prefix 出現至少 2 次，就代表有一個 connected group
- 題目說重複字串也算不同單字，所以同 prefix 的出現次數就是 group 的大小
我的寫法用 pre 記錄目前正在看的 prefix，用 first 來確保「同一個 prefix」只會被計數一次。
只要我看到某個 prefix 第一次重複出現，就 count++，後面再重複也不會再加。
所有變數
nword：把每個單字的前k個字母取出來後形成的新陣列（只收長度 >= k 的單字）count：答案，代表「至少兩個單字」的 prefix 群組數量pre：目前掃描到的 prefix 值，用來判斷是否換群組first：用來控制同一個 prefix 只計數一次（第一次遇到重複才加 1）
🪜 主要流程步驟
1. 把所有能用的單字轉成 k 長度的 prefix
我掃過 words：
- 如果
s.size() >= k，才有資格成為任何 group - 我就把
s.substr(0, k)放進nword - 長度 < k 的直接忽略
這一步做完後，nword 裡只剩「可能進入群組」的 prefix。
2. 排序 nword，讓相同 prefix 排在一起
我做 sort(nword.begin(), nword.end())。
排序後，相同 prefix 會變成一段連續區間，我接下來只要線性掃描就能判斷每一段是否有重複。
3. 掃描排序後的 prefix，遇到某個 prefix 至少出現兩次就 count++
我用三個概念控制計數：
pre：目前 prefix- 換 prefix 時，代表進入新的一段，要把
first = true重置 - 當
pre == t且first == true時，代表這段第一次看到重複- 我就
count++ - 把
first = false，避免同一段再重複加
- 我就
這樣每一段只要長度 >= 2，就一定會在「第二個出現」時被計數一次。
⏱️ 複雜度
- 時間複雜度：
O(m log m)m是長度 >= k 的單字數量。主要成本在排序nword。 - 空間複雜度：
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/contest/biweekly-contest-176/problems/number-of-prefix-connected-groups/