Unique Email Addresses — LeetCode #929 (Easy)
Tags: Array, Hash Table, String
Related patterns: Hash Map, Array
Brute Force approach
Time complexity: O(n²). Space complexity: O(1).
In the brute force approach, we will check each email address individually and apply the rules for dots and plus signs. This will allow us to generate the canonical form of each email and count unique addresses.
The complexity is O(n²) because for each email, we may be checking if it is already in the list of unique emails, leading to a nested loop-like behavior.
- Step 1: Initialize an empty list to store processed email addresses.
- Step 2: For each email in the input list, split it into local and domain parts using '@'.
- Step 3: In the local part, remove all dots and ignore everything after the first plus sign.
- Step 4: Combine the processed local part with the domain part to form the canonical email.
- Step 5: Add the canonical email to the list if it is not already present.
- Step 6: Return the size of the list as the count of unique email addresses.
1. Input: ['test.email+alex@leetcode.com', 'test.e.mail+bob.cathy@leetcode.com', 'testemail+david@lee.tcode.com']
2. Process 'test.email+alex@leetcode.com': local = 'testemail', domain = 'leetcode.com' → unique_emails = ['testemail@leetcode.com']
3. Process 'test.e.mail+bob.cathy@leetcode.com': local = 'testemail', domain = 'leetcode.com' → unique_emails = ['testemail@leetcode.com']
4. Process 'testemail+david@lee.tcode.com': local = 'testemail', domain = 'lee.tcode.com' → unique_emails = ['testemail@leetcode.com', 'testemail@lee.tcode.com']
5. Output: 2
Optimal Solution approach
Time complexity: O(n). Space complexity: O(n).
The optimal solution uses a HashSet to store unique email addresses directly, allowing us to efficiently check for duplicates as we process each email.
The complexity is O(n) because we process each email once and use a HashSet to store unique emails, which allows for average O(1) time complexity for insertions.
- Step 1: Initialize a HashSet to store unique email addresses.
- Step 2: For each email, split it into local and domain parts using '@'.
- Step 3: Remove all dots from the local part and ignore everything after the first plus sign.
- Step 4: Add the processed email directly to the HashSet.
- Step 5: Return the size of the HashSet as the count of unique email addresses.
1. Input: ['test.email+alex@leetcode.com', 'test.e.mail+bob.cathy@leetcode.com', 'testemail+david@lee.tcode.com']
2. Process 'test.email+alex@leetcode.com': local = 'testemail', domain = 'leetcode.com' → uniqueEmails = {'testemail@leetcode.com'}
3. Process 'test.e.mail+bob.cathy@leetcode.com': local = 'testemail', domain = 'leetcode.com' → uniqueEmails = {'testemail@leetcode.com'}
4. Process 'testemail+david@lee.tcode.com': local = 'testemail', domain = 'lee.tcode.com' → uniqueEmails = {'testemail@leetcode.com', 'testemail@lee.tcode.com'}
5. Output: 2
Key Insights
- The local part of an email can be modified by removing dots and ignoring characters after a plus sign.
- Using a HashSet allows for efficient storage and retrieval of unique email addresses.
Common Mistakes
- Not handling the plus sign correctly, leading to incorrect local name processing.
- Forgetting to remove dots from the local part before adding to the set.
Interview Tips
- Always clarify the rules of email processing before jumping into coding.
- Consider edge cases, such as emails without a plus sign or those with multiple dots.
- Explain your thought process clearly while coding; it helps the interviewer understand your approach.
