題目描述:
給定一個字串陣列 ideas,從中選兩個不同的字串,交換它們的首字母後,若兩個新字串都不在原陣列中,則這對是一個有效的公司名稱。求有效配對的總數。
解題思路:
(a, b)(a != b),計算交換後都不衝突的配對數:
a 和集合 b 中的不能配對(交換後仍存在於原陣列)。a 的大小為 sa,集合 b 的大小為 sb,兩集合的交集大小為 c。(sa - c) * (sb - c)。(a, b) 和 (b, a) 是不同的配對,需乘以 2。時間複雜度: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 中,需要如何調整算法?