[LeetCode]929. Unique Email Addresses

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：
字数统计：710 字 | 阅读时长：4 分钟

929. Unique Email Addresses

Every email consists of a local name and a domain name, separated by the @ sign.

For example, in alice@leetcode.com, alice is the local name, and leetcode.com is the domain name.

Besides lowercase letters, these emails may contain '.'s or '+'s.

If you add periods ('.') between some characters in the local name part of an email address, mail sent there will be forwarded to the same address without dots in the local name. For example, "alice.z@leetcode.com" and "alicez@leetcode.com" forward to the same email address. (Note that this rule does not apply for domain names.)

If you add a plus ('+') in the local name, everything after the first plus sign will be ignored. This allows certain emails to be filtered, for example m.y+name@email.com will be forwarded to my@email.com. (Again, this rule does not apply for domain names.)

It is possible to use both of these rules at the same time.

Given a list of emails, we send one email to each address in the list. How many different addresses actually receive mails?

Example 1:

1
2
3
Input: ["test.email+alex@leetcode.com","test.e.mail+bob.cathy@leetcode.com","testemail+david@lee.tcode.com"]
Output: 2
Explanation: "testemail@leetcode.com" and "testemail@lee.tcode.com" actually receive mails

Note:

  • 1 <= emails[i].length <= 100
  • 1 <= emails.length <= 100
  • Each emails[i] contains exactly one '@' character.
  • All local and domain names are non-empty.
  • Local names do not start with a '+' character.

大概解释一下题目：

邮箱地址中，本地名称部分可能包含“.”和“+”，其中“.”会直接被忽略掉，而第一个’+’之后，到‘@’之前，则会被截断；

输入：一个邮箱地址的数组；

输出：处理后的邮箱地址，不重复的有多少个；

方案一

  1. local name 和domain name 分开处理，否则domain name的‘.’可能会被错误去除；
  2. local name中可能包含多个“+”和多个“.”，“+”比较好处理，后面的直接截断；但是多个“.”就必须循环处理了；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int numUniqueEmails(vector<string>& emails) {
        set<string> email_set;
        for (string &email : emails) {
            int atindex = email.find('@');
            string local = email.substr(0, atindex);
            string domain = email.substr(atindex);
            
            int plusindex = local.find('+');
            if (plusindex != string::npos) {
                local.erase(plusindex, atindex-plusindex);
            }
            if(local.find('.') != string::npos) {
                local.erase(remove(local.begin(), local.end(), '.'), local.end());
            }
            email_set.insert(local+domain);
        }
        return email_set.size();
    }
};

result

Runtime: 36 ms, faster than 87.14% of C++ online submissions for Unique Email Addresses.
Memory Usage: 12.9 MB, less than 87.81% of C++ online submissions for Unique Email Addresses.

方案二：

方案一效果不是特别好，local部分其实循环处理了两次，可以把整个字符串从头到尾每个字符判断一遍；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int numUniqueEmails(vector<string>& emails) {
        unordered_set<string> emails_set;
        for (const string& email : emails) {
            string out;
            bool at = false;
            bool plus = false;
            for (char c : email) {
                if (c == '.') {
                    if (!at) continue;
                } else if (c == '@') {
                    at = true;          
                } else if (c == '+') {
                    if (!at) {
                        plus = true;
                        continue;
                    }
                }
                if (!at && plus) continue;
                out += c;        
            }      
            emails_set.insert(std::move(out));
        }
        return emails_set.size();
    }
};

result

Runtime: 32 ms, faster than 97.73% of C++ online submissions for Unique Email Addresses.
Memory Usage: 11.9 MB, less than 99.28% of C++ online submissions for Unique Email Addresses.

为了降低时间复杂度，降低空间复杂度，尝试各种方法，这一题提交了20次。。。