LeetCode 929. Unique Email Addresses

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

LeetCode 929. Unique Email Addresses 原题链接简单

作者：

yxc , 2018-11-03 02:06:36 , 所有人可见 , 阅读 4009

7

3

题目描述

每个邮箱地址都包含一个用户名和一个域名，用@隔开。

例如，在alice@leetcode.com中，alice是用户名，leetcode.com是域名。

除了小写字母之外，邮箱地址还包含'.'和'+'。

在发送邮件时：

用户名中的'.'会被忽略掉，例如"alice.z@leetcode.com"和"alicez@leetcode.com"会被发送到相同地址；
用户名中'+'及其后面的字符会被忽略掉，例如"m.y+name@email.com"和"my@email.com"会被发送到相同地址；

这两种规则可以同时被使用。

给出一个邮箱地址列表emails，我们给每个地址发一封邮件。请问共有多少个不同的地址会收到邮件？

注意：

1 <= emails[i].length <= 100
1 <= emails.length <= 100
每一个emails[i]只会包含一个@

样例

输入：["test.email+alex@leetcode.com","test.e.mail+bob.cathy@leetcode.com","testemail+david@lee.tcode.com"]
输出：2
解释："testemail@leetcode.com" 和 "testemail@lee.tcode.com" 是最终收到邮件的地址。

算法

(哈希表，字符串处理) $O(n)$

遍历emails中的每个邮箱地址，然后依次进行如下操作：

分别找出用户名和域名；
从前往后遍历用户名的每个字符，如果遇到'+'，则直接截断；如果遇到'.'，则忽略该字符；
将新用户名和域名重新组合，再插入哈希表中；

最终哈希表中不同元素的个数就是答案。

时间复杂度分析：'emails'中的每个邮箱地址只会遍历2遍，且哈希表的插入和查找的时间复杂度均是 $O(L)$，$L$是字符串长度。所以总时间复杂度是 $O(n)$，$n$ 表示字符串总长度。

C++ 代码

class Solution {
public:
    int numUniqueEmails(vector<string>& emails) {
        unordered_set<string> S;
        for (auto email : emails)
        {
            string local, domain;
            int k = 0;
            while (email[k] != '@') k ++ ;
            local = email.substr(0, k);
            domain = email.substr(k + 1);
            string newLocal;
            for (auto c : local)
            {
                if (c == '+') break;
                if (c != '.') newLocal += c;
            }
            S.insert(newLocal + '@' + domain);
        }
        return S.size();
    }
};

7 评论

歪嘴战神叁叁叁 2019-08-03 19:20

我也想要一份纯java解法的代码谢谢y神~

yxc 2019-08-03 19:29

我直接从leetcode的discuss里搜的，直接从里面找就好~

胡歌-此生不换 2022-10-06 21:22

class Solution {
public int numUniqueEmails(String[] s) {
        // unordered_map<string, int> hash;
        HashSet<String> hash = new HashSet<>();

        for(String c: s)
        {
            // int i = c.find('+');
            // string a = c.substr(0, i);
            // while(a.find('.') != -1)
            // {
            //     i = a.find('.');
            //     a = a.substr(0, i) + a.substr(i + 1);  // 去除 '.'
            // }
            // hash[a]++;

            int i = c.indexOf('+');
            String a;
            if(i != -1) a = c.substring(0, i);
            else
            {
                int j = c.indexOf('@');
                a = c.substring(0, j);
            }

            while(a.indexOf('.') != -1){
                i = a.indexOf('.');
                a = a.substring(0, i) + a.substring(i + 1, a.length());
            }

            int j = c.indexOf('@');
            String b = c.substring(j, c.length());
            // while(b.indexOf('.') != -1 && b.indexOf('.') != b.length() - 4){        // '.'  不是 com 前面的 '.' 的话要删除的哦
            //     i = b.indexOf('.');
            //     b = b.substring(j, i) + b.substring(i + 1, b.length());
            // }

            hash.add(a + b);
        }
        for(String c: hash)
            System.out.println(c);

        return hash.size();
    }
};