哈希表题目：独特的电子邮件地址

题目

标题和出处

标题独特的电子邮件地址

出处929. 独特的电子邮件地址

难度

3 级

题目描述

要求

每个有效的电子邮件都由一个本地名称和一个域名组成以 $\text{‘@’}$ 符号分隔。除了小写字母电子邮件还可能包含一个或多个 $\text{‘.’}$ 和 $\text{‘+’}$。

• 例如在 $\text{"alice@leetcode.com"}$ 中$\text{"alice"}$ 是本地名称而 $\text{"leetcode.com"}$ 是域名。

如果在电子邮件地址的本地名称中的某些字符之间添加句点 $\text{‘.’}$则发往那里的邮件将会转发到本地名称中没有点的同一地址。请注意此规则不适用于域名。

• 例如$\text{"alice.z@leetcode.com"}$ 和 $\text{"alicez@leetcode.com"}$ 会转发到同一电子邮件地址。

如果在本地名称中添加加号 $\text{‘+’}$则会忽略第一个加号后面的所有内容。这允许过滤某些电子邮件请注意此规则不适用于域名。

• 例如$\text{m.y+name@email.com}$ 将转发到 $\text{my@email.com}$。

可以同时使用这两个规则。

给定字符串数组 $\text{emails}$我们会向每个 $\text{emails[i]}$ 发送一封电子邮件返回实际收到邮件的不同地址数量。

示例

示例 1

输入$\text{["test.email+alex@leetcode.com","test.e.mail+bob.cathy@leetcode.com","testemail+david@lee.tcode.com"]}$
输出$\text{2}$
解释实际收到邮件的是 $\text{"testemail@leetcode.com"}$ 和 $\text{"testemail@lee.tcode.com"}$。

示例 2

输入$\text{emails = ["a@leetcode.com","b@leetcode.com","c@leetcode.com"]}$
输出$\text{3}$

数据范围

• $\text{1}\le \text{emails.length}\le \text{100}$
• $\text{1}\le \text{emails[i].length}\le \text{100}$
• $\text{emails[i]}$ 由小写英语字母、$\text{‘+’}$、$\text{‘.’}$ 和 $\text{‘@’}$ 组成
• 每个 $\text{emails[i]}$ 都包含有且仅有一个 $\text{‘@’}$ 字符
• 所有的本地名称和域名都是非空的
• 本地域名的第一个字符不会是 $\text{‘+’}$

解法

思路和算法

为了计算实际收到邮件的不同地址数量需要对每个电子邮件地址转换成实际收到邮件的地址使用哈希集合存储实际收到邮件的地址。

由于实际收到邮件的地址和原地址的区别只可能发生在本地名称因此只要对本地名称进行处理得到实际收到邮件的地址的本地名称然后拼接 $\text{‘@’}$ 符号和域名即可得到实际收到邮件的完整地址。

由于哈希集合中的元素都不相同因此在对每个电子邮件地址转换成实际收到邮件的地址并存入哈希集合之后哈希集合中的元素个数即为实际收到邮件的不同地址数量。

代码

class Solution {
    public int numUniqueEmails(String[] emails) {
        Set<String> set = new HashSet<String>();
        for (String email : emails) {
            StringBuffer sb = new StringBuffer();
            int atIndex = email.indexOf('@');
            for (int i = 0; i < atIndex; i++) {
                char c = email.charAt(i);
                if (c == '+') {
                    break;
                }
                if (c == '.') {
                    continue;
                }
                sb.append(c);
            }
            sb.append(email.substring(atIndex));
            set.add(sb.toString());
        }
        return set.size();
    }
}

复杂度分析

• 时间复杂度$O(\sum l_e)$即数组 $\text{emails}$ 中所有电子邮件地址的长度之和。需要 $O(\sum l_e)$ 的时间遍历所有电子邮件地址对于每个电子邮件地址生成实际收到邮件的地址和存入哈希表的时间为该电子邮件地址对应的实际收到邮件的地址的长度其长度不会超过原始电子邮件地址的长度因此总时间复杂度为 $O(\sum l_e)$。

• 空间复杂度$O(\sum l_e)$即数组 $\text{emails}$ 中所有电子邮件地址的长度之和。需要使用哈希表存储每个电子邮件地址对应的实际收到邮件的地址最坏情况下每个电子邮件地址对应的实际收到邮件的地址都和原始电子地址邮件地址相同且任意两个电子邮件地址都不同此时哈希表的空间为所有电子邮件地址的长度之和。