Description
給定字串陣列
ideas，每個字串代表一個公司名。選擇兩個名字ideaA和ideaB，交換它們的首字母得到ideaA'和ideaB'。若兩個新名字都不在原始ideas中，則(ideaA', ideaB')是一個有效的公司名組合。回傳不同的有效名稱數量。
Example:
Input: ideas = [“coffee”,“donuts”,“time”,“toffee”] Output: 6 （如 (“doffee”,“conuts”), (“toffee”,“cime”) 等）
Intuition#
核心思路：按首字母分組，對任意兩組（首字母 a 和 b），計算「交換後互不衝突」的配對數。若 suffix 同時出現在 a 組和 b 組，交換後兩個新名字都會衝突，所以要排除共同 suffix。
- 將所有 idea 按首字母分成 26 組，每組存 suffix Set
- 對任意兩組 (i, j)，共同 suffix 的數量為
mutual = |set_i ∩ set_j| - 可配對的 suffix 數量：
(|set_i| - mutual) * (|set_j| - mutual) - 乘以 2（因為 (A, B) 和 (B, A) 是不同的）
Approaches#
1: Brute Force (TLE)#
- 概念: 枚舉所有 idea 對，交換首字母檢查是否有效
- 時間複雜度:
O(n^2 * m)- n 為 idea 數，m 為平均長度 - 空間複雜度:
O(n * m)- HashSet 儲存所有 idea
class Solution {
fun distinctNames(ideas: Array<String>): Long {
val ideaSet = ideas.toHashSet()
var count = 0L
for (i in ideas.indices) {
for (j in i + 1 until ideas.size) {
val newA = ideas[j][0] + ideas[i].substring(1)
val newB = ideas[i][0] + ideas[j].substring(1)
if (newA !in ideaSet && newB !in ideaSet) {
count += 2
}
}
}
return count
}
}⭐2: Group by Initial + Mutual Exclusion#
- 概念: 按首字母分 26 組，對每對組計算共同 suffix 數量，用排除法計算有效配對
- 時間複雜度:
O(n * m + 26^2 * n)- 分組 O(n*m)，計算交集最壞 O(26^2 * max_group_size) - 空間複雜度:
O(n * m)- 儲存所有 suffix Set
class Solution {
fun distinctNames(ideas: Array<String>): Long {
// 按首字母分組，存 suffix
val groups = Array(26) { HashSet<String>() }
for (idea in ideas) {
groups[idea[0] - 'a'].add(idea.substring(1))
}
var count = 0L
for (i in 0 until 26) {
for (j in i + 1 until 26) {
// 計算共同 suffix 數量
var mutual = 0
for (suffix in groups[i]) {
if (suffix in groups[j]) mutual++
}
val uniqueI = groups[i].size - mutual
val uniqueJ = groups[j].size - mutual
count += 2L * uniqueI * uniqueJ
}
}
return count
}
}為什麼只需要考慮共同 suffix？假設 suffix “offee” 同時出現在 ‘c’ 組（“coffee”）和 ’t’ 組（“toffee”）。交換首字母後 “toffee” 和 “coffee” 都已存在於原始 ideas，所以這對 suffix 不能配對。只有兩組中「互不共享」的 suffix 才能安全交換。
🔑 Takeaways#
- Pattern: 大量配對計數 -> 分組 + 排除共同元素
- 關鍵技巧: 按首字母分組將 O(n^2) 問題降維到 O(26^2 _ group_size)；「互斥計數」公式
(|A| - |A∩B|) _ (|B| - |A∩B|)是分組配對的通用模式