解題說明
Unique Email Addresses
題目描述:
每封電子郵件地址由「本地名稱」和「域名」組成(用 '@' 分隔)。本地名稱中的規則:
'.'字元會被忽略(a.b等同ab)。'+'後面的所有字元會被忽略(a+foo等同a)。
這些規則只適用於本地名稱,不適用於域名。
給定一組郵件地址,求實際有多少個不同的收件地址。
解題思路:
- 對每個郵件地址,先用
'@'分割成本地名稱和域名。 - 對本地名稱:移除所有
'.',截斷'+'後面的部分。 - 將處理後的「本地名稱 + @ + 域名」加入雜湊集合。
- 集合的大小即為答案。
C++ 解法
複雜度分析
時間複雜度:O(n * m) — 其中 n 是郵件數量,m 是每封郵件的平均長度。每封郵件需要線性掃描處理。
空間複雜度:O(n * m) — 雜湊集合最多存放 n 個處理後的郵件地址。
虛擬碼
1. Create an empty hash set. 2. For each email: a. Split at '@' into local and domain. b. Truncate local at first '+'. c. Remove all '.' from local. d. Insert (cleaned_local + '@' + domain) into set. 3. Return size of set.
其他解法
逐字元構建:O(n * m) 時間、O(n * m) 空間。不使用 find 和 substr,改為逐字元遍歷,遇到 '.' 跳過、遇到 '+' 停止本地名稱處理、遇到 '@' 開始複製域名。常數因子略小。
正則表達式:使用 regex 處理本地名稱。程式碼更簡潔但效率較低,適合快速原型。
延伸思考
- 如果本地名稱的規則因不同郵件服務商而異(例如 Gmail 忽略
.,但其他不一定),如何修改設計? - 如果輸入量非常大(百萬封郵件),如何優化記憶體使用?
- 此題的字串處理邏輯在實際系統中有哪些安全隱患(例如郵件欺騙)?