LeetCode 929. 独特的电子邮件地址
题目描述
题意分析
邮箱由
@前的本地名与@后的域名组成。题目只允许对本地名应用两条规则：忽略点号，忽略第一个加号及其后面的内容。域名保持原样，最后统计这些地址实际对应多少个不同目标。
解法：规范化 + 哈希集合去重
核心思路
[!blue]
先定位
@，把本地名和域名分开，防止将局部规则误用到整个地址。随后从左到右扫描本地名：遇到.只跳过当前字符，遇到+则结束扫描，其他字符按顺序放入缓冲区。扫描过程中，缓冲区恰好保存已经处理的本地名前缀中仍有意义的字符；一旦遇到第一个
+，其后的所有本地名字符都不再影响目标，因此可以直接停止。最后拼回规范本地名、@和原域名，得到该地址的唯一规范表示。两个地址按题目规则指向同一目标，当且仅当它们的规范本地名相同、域名也相同。保留中间的
@能明确区分这两部分，所以用整个规范地址作为集合键，既会合并等价地址，也不会合并不同目标。集合大小就是答案。
解题步骤
- 找到 @ 并分开本地名与域名。
- 扫描本地名，跳过点号，在首个加号处停止。
- 拼回规范本地名、@ 和原域名。
- 加入集合并返回集合大小。
本地名没有加号或点号时，扫描会完整保留它；多个加号只需处理第一个。题目保证地址格式有效，代码据此定位唯一的
@并取出两部分。
代码实现
class Solution {
public int numUniqueEmails(String[] emails) {
Set<String> set = new HashSet<>();
for (String email : emails) {
// 先分离本地名与域名，忽略规则只作用于本地名。
int at = email.indexOf('@');
String local = email.substring(0, at);
String domain = email.substring(at + 1);
StringBuilder sb = new StringBuilder();
for (int i = 0; i < local.length(); i++) {
char c = local.charAt(i);
// 加号及后面内容全部忽略，点号则仅跳过自身。
if (c == '+') {
break;
}
if (c == '.') {
continue;
}
sb.append(c);
}
set.add(sb + "@" + domain);
}
return set.size();
}
}
func numUniqueEmails(emails []string) int {
set := make(map[string]bool)
for _, email := range emails {
// 先分离本地名与域名，忽略规则只作用于本地名。
at := 0
for at < len(email) && email[at] != '@' {
at++
}
local := email[:at]
domain := email[at+1:]
buf := make([]byte, 0, len(local))
for i := 0; i < len(local); i++ {
c := local[i]
// 加号及后面内容全部忽略，点号则仅跳过自身。
if c == '+' {
break
}
if c == '.' {
continue
}
buf = append(buf, c)
}
set[string(buf)+"@"+domain] = true
}
return len(set)
}
复杂度分析
- 时间复杂度：期望 $O(S)$，S 为输入地址总字符数。
- 空间复杂度：$O(S)$，保存规范地址与临时缓冲。
关键点总结
[!green]
- 两条忽略规则只作用于本地名。
- 加号表示截断，点号表示跳过，两种操作不同。
- 规范化后使用完整地址去重。
易错点总结
[!yellow]
- 修改域名中的点号，会合并本来不同的域名。
- 加号表示截断整个后缀，点号只表示跳过自身，不能交换处理方式。
- 拼接时省略
@会丢失两部分边界，使不同的本地名与域名组合产生同一个键。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 71. 简化路径 | 中等 | 同样按规则规范化字符串后判等，本题只处理邮箱本地名的点号和加号，不能把规则扩展到域名。 |
| 609. 在系统中查找重复文件 | 中等 | 同样先求等价内容键再用集合或映射聚合，本题键是规范化邮箱，原题键是文件内容。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！