algoadvance

Leetcode 929. Unique Email Addresses

Problem Statement

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 also contain '.' or '+'.

  1. If you add periods ('.') to 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 address.
  2. If you add a plus ('+') to the local name, it will ignore everything after the plus sign. This allows certain email filtering. For example, "alice+leetcode@leetcode.com" and "alice@leetcode.com" forward to the same email address.

Given a list of email addresses, we need to determine the number of unique addresses.

Clarifying Questions

  1. Input Format: List of strings representing the emails.
  2. Output Format: A single integer representing the number of unique email addresses after normalization.

Code

#include <iostream>
#include <unordered_set>
#include <vector>

class Solution {
public:
    int numUniqueEmails(std::vector<std::string>& emails) {
        std::unordered_set<std::string> uniqueEmails;
        
        for (const std::string& email : emails) {
            std::string localName;
            std::string domainName;
            bool atSymbol = false;
            bool ignoreRest = false;
            
            for (char c : email) {
                if (c == '@') {
                    atSymbol = true;
                }
                
                if (atSymbol) {
                    domainName += c;
                } else {
                    if (c == '+') {
                        ignoreRest = true;
                    }
                    if (!ignoreRest && c != '.') {
                        localName += c;
                    }
                }
            }
            
            uniqueEmails.insert(localName + domainName);
        }
        
        return uniqueEmails.size();
    }
};

int main() {
    Solution sol;
    std::vector<std::string> emails = {
        "test.email+alex@leetcode.com", 
        "test.e.mail+bob.cathy@leetcode.com", 
        "testemail+david@lee.tcode.com"
    };
    std::cout << sol.numUniqueEmails(emails) << std::endl;  // Output should be 2
    return 0;
}

Strategy

  1. Initialization: We initialize an unordered set (uniqueEmails) to store the unique email addresses.
  2. Traversal: We iterate through each email in the provided list.
    • We split the email into the local name and the domain name.
    • We ignore any characters in the local name part after a '+'.
    • We also ignore '.' characters in the local name.
  3. Combining Local and Domain Names: Combine the processed local name and the domain name, then insert it into the uniqueEmails set.
  4. Result: The size of the uniqueEmails set represents the number of unique email addresses.

Time Complexity

The overall time complexity is O(n*m), where n is the number of emails in the list, and m is the average length of an email address. This results from processing each character in each email once. The unordered_set operations (insert and lookup) are average O(1), making the solution efficient.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI