LeetCode 929. 独特的电子邮件地址

2020-09-24 HGNULB 约 8 分钟

文章信息 6 个分类 3 个标签

分类

题目描述

✅ 929. 独特的电子邮件地址

题意分析

每个邮箱地址由 @ 分成本地名（前）和域名（后）两部分。投递时会先按两条规则改写本地名：本地名中的所有 . 全部忽略；本地名中第一个 + 及其之后的全部字符忽略。域名部分原样保留，不做任何改写。给一组地址，问最终会向多少个不同的地址投递。

两条规则的作用范围是全题最容易读错的地方：它们只适用于 @ 之前。域名里的 . 是必须保留的——leetcode.com 与 leetcodecom 是两个完全不同的域名。所以第一步一定是先按 @ 切开，再只对左半边动手。

两条规则的优先级也要理清：+ 之后的内容整体作废，所以那部分里的 . 根本不需要考虑。换句话说，一旦遇到 + 就可以立刻停止处理本地名，不必先删点再截断。

「有多少个不同的地址」是去重计数，天然对应哈希集合：把每个地址规范化成唯一的标准形式，扔进集合，最后取集合大小。规范化的意义在于把「等价」变成「相等」——只要两个地址会投递到同一处，它们的规范形式就必须逐字符相同。

约束里地址数量最多 100、每个地址长度最多 100，规模极小；题目还保证每个地址恰好含一个 @，且 @ 前后都非空，所以不必处理缺失 @ 或本地名为空的畸形输入。

边界：本地名以 + 开头（如 "+abc@x.com"）时规范化后本地名为空串，这仍是合法结果，只要与其他地址区分开即可；本地名全是点（如 "a.b.c@x.com"）时点被删光；同一个规范形式出现多次只算一个。

解法：规范化 + 哈希集合去重

核心思路

直觉做法是两两比较所有地址是否等价，$O(n^2)$ 次比较，每次还要各自解析一遍。规模小的时候能过，但它把「等价关系」当成了需要反复判定的东西，浪费而且容易写出不一致的比较逻辑。

更好的角度是：等价关系可以用一个代表元来表示。既然规则是确定的、单向的，就为每个地址计算出唯一的「投递目标」字符串，然后去重。这样比较从 $O(n^2)$ 次成对判定降成 $n$ 次规范化加哈希，而且逻辑集中在一处，不会出现「A 等价 B、B 等价 C 但 A 不等价 C」这类实现不一致。

不变量：集合中的每个元素都是一个真实的投递目标，且两个原始地址被投递到同一处，当且仅当它们的规范形式相同。因此集合大小恰好等于不同投递目标的数量。

规范化的具体过程是一次线性扫描：先用 indexOf('@') 找到分隔点，把地址切成 local 与 domain；然后遍历 local，遇到 + 立即 break（后面全部作废），遇到 . 直接 continue（跳过不写入），其余字符追加到结果缓冲区；最后拼回 规范本地名 + "@" + domain。

拼接时必须保留 @。如果只把本地名和域名直接连起来，"ab@c.com" 与 "a@bc.com" 会得到同一个字符串 "abc.com"，两个不同的地址被错误合并。分隔符的作用就是防止这种跨边界的歧义。

用 StringBuilder（Go 里用 []byte 缓冲）而不是在循环里反复做字符串拼接：字符串不可变，逐字符 += 会在每次追加时复制整个前缀，把 $O(L)$ 的规范化退化成 $O(L^2)$。

解题步骤

准备一个哈希集合：它既承担去重也承担计数，最后 size() 就是答案，不需要额外的计数变量。

对每个地址先定位 @：int at = email.indexOf('@')。题目保证恰有一个 @，所以第一个出现的位置就是分隔点。

切出 local = email.substring(0, at) 与 domain = email.substring(at + 1)：at + 1 而不是 at，否则域名会带上 @ 本身，虽然不影响去重的正确性，但拼接时会出现两个 @，可读性变差。

遍历 local 做规范化：遇到 '+' 执行 break——不是 continue，因为 + 之后的字符全部作废，包括其中的点和字母；遇到 '.' 执行 continue——不是 break，点只是被删掉，后面的字符仍然有效。这两个关键字用反是本题最典型的错误。

其余字符追加进缓冲区：只有非 +、非 . 且在 + 之前的字符才构成规范本地名。

拼成 规范本地名 + "@" + domain 放进集合：域名不做任何处理，直接原样接上。

返回集合大小。

以 emails = ["test.email+alex@leetcode.com", "test.e.mail+bob.cathy@leetcode.com", "testemail+david@lee.tcode.com"] 走一遍，正确答案是 2。

第 1 个地址 "test.email+alex@leetcode.com"：@ 在下标 15，local = "test.email+alex"，domain = "leetcode.com"。扫描 local：t、e、s、t 依次写入；下标 4 是 .，跳过；e、m、a、i、l 写入；下标 10 是 +，立即 break，后面的 alex 全部作废。规范本地名为 "testemail"，拼成 "testemail@leetcode.com" 入集合。集合大小 1。

第 2 个地址 "test.e.mail+bob.cathy@leetcode.com"：local = "test.e.mail+bob.cathy"，domain = "leetcode.com"。扫描时两个 . 都被跳过，得到 "teste" 再接 "mail" 即 "testemail"；遇到 + 后 "bob.cathy" 整段作废——注意这里面还有一个 .，但因为已经 break，根本不会被处理。拼成 "testemail@leetcode.com"，与第 1 个完全相同，集合去重后仍是 1。

第 3 个地址 "testemail+david@lee.tcode.com"：local = "testemail+david" 规范化后是 "testemail"，看起来和前两个一样；但 domain = "lee.tcode.com" 中的点必须保留，与 "leetcode.com" 不是同一个域名。拼成 "testemail@lee.tcode.com" 入集合，集合大小变成 2。

返回 2。这个用例把三个陷阱一次性覆盖了：本地名的点要删、+ 之后整段作废（包括其中的点）、域名的点必须保留。如果误把规则应用到域名上，第 3 个地址会被并进前两个，答案错成 1。

代码实现

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)$。哈希集合最坏要存下 $n$ 个规范化地址，长度合计不超过 $S$；每个地址处理时的缓冲区可复用，属于同阶开销。

关键点总结

「有多少个本质不同的 X」的通用解法是规范化 + 集合去重：把等价关系折叠成代表元，让 $O(n^2)$ 的两两判定变成 $n$ 次映射，也杜绝了比较逻辑不自洽的隐患。

规则的作用域必须先划清。本题两条规则只作用于 @ 之前，域名原样保留；先切分再处理，比在整串上打补丁可靠得多。

+ 与 . 的语义不同：前者截断（break），后者删除（continue）。能一句话说清「为什么一个用 break 一个用 continue」，就说明真的读懂了规则。

拼接时必须保留 @ 作为分隔符，否则 "ab@c.com" 与 "a@bc.com" 会被合并成同一个键，跨边界歧义是这类拼接键的通病。

构造字符串用 StringBuilder / []byte 缓冲，避免循环内不可变字符串反复复制导致的 $O(L^2)$。

面试视角：这题代码不难，考的是审题的精细度。主动指出「+ 后面的点不需要处理」和「域名的点必须保留」两个细节，比写得快更能拿分。

易错点总结

把规则也应用到域名上："testemail+david@lee.tcode.com" 的域名点被删成 "leetcode.com"，会与 "test.email+alex@leetcode.com" 合并，示例答案从 2 错成 1。

遇到 + 用 continue 而不是 break："test.email+alex@leetcode.com" 会规范化成 "testemailalex"，与 "test.e.mail+bob.cathy@leetcode.com" 规范化出的 "testemailbobcathy" 不同，答案从 2 错成 3。

遇到 . 用 break 而不是 continue："test.email+alex@leetcode.com" 会只保留 "test"，把本该不同的地址大量误合并。

切域名时写成 substring(at)：域名带上了 @，拼接后出现 "testemail@@leetcode.com"。去重结果虽然仍正确，但一旦有人改成不加分隔符的拼接就会立刻出错。

拼接时省掉 @："ab@c.com" 与 "a@bc.com" 都变成 "abc.com"，两个不同地址被计成一个。

用 split("@") 后取 [1] 而不校验：本题保证只有一个 @，但若输入含多个，split 会丢掉后面的部分；用 indexOf + substring 语义更明确。

在 + 之后仍继续删点：功能上不影响结果（那段本就作废），但会白白多扫一段，且容易让人误以为 + 后的内容参与规范化，进而写出 + 用 continue 的错误版本。

用列表存规范化结果再逐一比对去重：$O(n^2)$ 的比较，且极易漏掉「已存在就不加」的判断，最终计数偏大。集合天然去重，没有理由不用。

循环内用 String 拼接构造本地名：每次 local += c 都复制整个前缀，单个地址的规范化从 $O(L)$ 退化到 $O(L^2)$。

误以为要区分大小写之外的规则（如去掉空格、忽略大小写）：题目只给了两条规则，自行加规则会把 "A@x.com" 与 "a@x.com" 错误合并。

返回投递地址列表而不是数量：题目问的是「多少个不同地址」，返回集合本身或原数组长度都是审题错误。

相似题目

题目	难度	考察点
49. 字母异位词分组	中等	同为「规范化成代表元再归并」，代表元是排序后的串或字符计数签名
242. 有效的字母异位词	简单	只判两个串是否等价，用计数数组比较即可，无需构造代表元
205. 同构字符串	简单	等价性由双向映射定义，无法用简单规范化表示，需要两张哈希表互相校验