HardRating 2305
2306. Naming a Company
arrayhash-tablestringbit-manipulationenumeration
解題說明
Naming a Company
題目描述:
給定一個字串陣列 ideas,從中選兩個不同的字串,交換它們的首字母後,若兩個新字串都不在原陣列中,則這對是一個有效的公司名稱。求有效配對的總數。
解題思路:
- 按首字母分組:將所有字串按首字母分成 26 個集合,每個集合存放去掉首字母後的後綴。
- 對每對首字母
(a, b)(a != b),計算交換後都不衝突的配對數:- 後綴同時出現在集合
a和集合b中的不能配對(交換後仍存在於原陣列)。 - 設集合
a的大小為sa,集合b的大小為sb,兩集合的交集大小為c。 - 有效配對數 =
(sa - c) * (sb - c)。 - 由於
(a, b)和(b, a)是不同的配對,需乘以 2。
- 後綴同時出現在集合
- 累加所有首字母對的結果。
C++ 解法
複雜度分析
時間複雜度:O(n * m) — n 為字串數量,m 為平均字串長度。對每對首字母比較交集需遍歷較小集合,總計所有遍歷次數為 O(n),每次雜湊查詢 O(m)。外層 26*25/2 = 325 對首字母為常數。
空間複雜度:O(n * m) — 儲存所有後綴的雜湊集合。
虛擬碼
1. Group suffixes by first character into 26 sets 2. For each pair of first characters (a, b) where a < b: a. Count common suffixes between groups[a] and groups[b] b. sa = |groups[a]| - common c. sb = |groups[b]| - common d. ans += 2 * sa * sb 3. Return ans
其他解法
位元遮罩優化 O(n * 26):對每個後綴,用 26 位的 bitmask 記錄它出現在哪些首字母分組中。然後對每對 (a, b),遍歷後綴集合統計交集。在後綴重複率高時更快。
暴力枚舉 O(n^2 * m):檢查所有字串對,模擬交換首字母並在集合中查找。時間複雜度過高,不可行。
延伸思考
- 如果允許交換任意位置的字元(不限首字母),問題難度如何變化?
- 如何優化使得在後綴集合極大時仍高效?(提示:考慮遍歷較小的集合)
- 如果字串可以重複出現在
ideas中,需要如何調整算法?