This problem looks busy at first, but the accepted solution is built around one steady invariant. For 929. Unique Email Addresses, the solution in this repository is mainly a straightforward implementation solution.
Guide
What?
We want to turn the problem statement into a smaller set of decisions the computer can repeat safely. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: straightforward implementation.
Guide
When?
This pattern shows up when the brute force version has too many repeated checks, too many possible branches, or too much bookkeeping to do by hand. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are numUniqueEmails.
Guide
Why?
The win comes from making each line carry responsibility: store the useful state, discard the rest, keep moving.
- A set is doing the membership or uniqueness work, which keeps the main loop readable.
- Substring checks are convenient but not free, so they are part of the real complexity story.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Start from the smallest reliable state.
- Expand one legal move at a time.
- Cache, count, or merge information as soon as it becomes settled.
- Let the final stored value answer the original question.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(C), where C is the total content of emails.
- Space: O(C).
Guide
C++ Solution
Your submission
The accepted solution
01/**
02Every email consists of a local name and a domain name, separated by the @ sign.
03
04For example, in alice@leetcode.com, alice is the local name, and leetcode.com is the domain name.
05
06Besides lowercase letters, these emails may contain '.'s or '+'s.
07
08If 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.)
09
10If 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.)
11
12It is possible to use both of these rules at the same time.
13
14Given a list of emails, we send one email to each address in the list. How many different addresses actually receive mails?
15
16
17
18Example 1:
19
20Input: ["test.email+alex@leetcode.com","test.e.mail+bob.cathy@leetcode.com","testemail+david@lee.tcode.com"]
21Output: 2
22Explanation: "testemail@leetcode.com" and "testemail@lee.tcode.com" actually receive mails
23
24
25Note:
26
271 <= emails[i].length <= 100
281 <= emails.length <= 100
29Each emails[i] contains exactly one '@' character.
30**/
31
32/**
33Approach 1: Canonical Form
34Intuition and Algorithm
35
36For each email address, convert it to the canonical address that actually receives the mail. This involves a few steps:
37
38Separate the email address into a local part and the rest of the address.
39
40If the local part has a '+' character, remove it and everything beyond it from the local part.
41
42Remove all the zeros from the local part.
43
44The canonical address is local + rest.
45
46After, we can count the number of unique canonical addresses with a Set structure.
47
48Complexity Analysis
49
50Time Complexity: O(C), where C is the total content of emails.
51
52Space Complexity: O(C).
53**/
54
55/**
56Your runtime beats 71.33 % of cpp submissions.
57**/
58
59class Solution {
60public:
61 int numUniqueEmails(vector<string>& emails) {
62 set<string> filtered;
63
64 for(vector<string>::iterator it = emails.begin() ; it != emails.end(); ++it){
65 string s = (*it);
66 string localname = s.substr(0, s.find("+"));
67 string domainname = s.substr(s.find("@"), s.size());
68 while(true){
69 int dot = localname.find(".");
70 // cout << dot << endl;
71 if(dot==-1){
72 break;
73 }else{
74 localname.erase(dot, 1); //in-place
75 // localname.replace(dot, 1, ""); //in-place
76 }
77 }
78 filtered.insert(localname+domainname);
79 // cout << localname+domainname << endl;
80 }
81
82 return filtered.size();
83 }
84};Cost