[leetcode #929] Unique Email Addresses

Problem

Every valid email consists of a local name and a domain name, separated by the '@' sign. Besides lowercase letters, the email may contain one or more '.' or '+'.

For example, in "alice@leetcode.com", "alice" is the local name, and "leetcode.com" is the domain name.
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. Note that this rule does not apply to domain names.

For example, "alice.z@leetcode.com" and "alicez@leetcode.com" forward to the same email address.
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. Note that this rule does not apply to domain names.

For example, "m.y+name@email.com" will be forwarded to "my@email.com".
It is possible to use both of these rules at the same time.

Given an array of strings emails where we send one email to each email[i], return the number of different addresses that actually receive mails.

Example 1:

Input: emails = ["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.

Example 2:

Input: emails = ["a@leetcode.com","b@leetcode.com","c@leetcode.com"]
Output: 3

Constraints:

・ 1 <= emails.length <= 100
・ 1 <= emails[i].length <= 100
・ email[i] consist of lowercase English letters, '+', '.' and '@'.
・ Each emails[i] contains exactly one '@' character.
・ All local and domain names are non-empty.
・ Local names do not start with a '+' character.

Idea

난이도 Hard인 문제가 나오면 "다음에 풀자"고 미루다가 Easy인 문제만 풀게 되는 악순환이 찾아왔다. 시간을 좀 들여서라도 leetcode 문제 푸는 걸 게을리하지 말아야겠다.

문제에서 요구하는 건 주어진 rule에 맞게 local name을 바꾸고, domain name과 결합해 forward되는 고유한 이메일 주소의 개수를 구하는 것이다. local name에 적용되는 rule은 간단하다. '+' 이후의 string은 무시하고, '+' 앞의 string에서 '.'를 전부 제거하면 된다. domain name은 rule이 적용되지 않아 주어진 domain을 그대로 활용하면 된다.

java library에서 string을 다루는 함수인 indexOf, substring, replaceAll을 사용하면 쉽게 풀 수 있다. replaceAll에 들어가는 인자는 regex이므로 "."가 아닌 "\."를 넣어주도록 해야 한다.

rule을 적용한 local name을 map의 key로 하고, domain name을 각 key의 value에 해당하는 set에 넣어준다. 주어진 email을 모두 탐색하여 map을 완성한 뒤, map의 value인 set의 크기를 전부 더해 리턴하면 된다.

알고리즘은 다음과 같다.

1. @를 기준으로 local name과 domain name을 분리한다.
2. local name에서 '+' 앞의 substring을 구하고 '.'을 전부 제거한 뒤 map의 key로 사용될 string을 구한다.
3. 2에서 구한 string을 key로 하고 string set을 value로 한다. 각 local name에 해당하는 domain name을 set에 넣어준다.
4. map의 value인 set의 크기를 전부 더하여 결과값을 리턴한다.

Solution

class Solution {
    public int numUniqueEmails(String[] emails) {
        Map<String, Set<String>> map = new HashMap<>();

    	for (int i=0; i < emails.length; i++) {
            String email = emails[i];
            int at = email.indexOf("@");
            String local = email.substring(0, at);
            String domain = email.substring(at+1);
            String modified;
            if (local.contains("+")) {
                modified = local.substring(0, local.indexOf("+")).replaceAll("\\.", "");
            } else {
                modified = local.replaceAll("\\.", "");
            }
      
            if (!map.containsKey(modified)) {
                map.put(modified, new HashSet<>(Arrays.asList(domain)));
            } else {
                map.get(modified).add(domain);
            }
        }
  
    	int res = 0;
    	for (Set set : map.values()) {
            res += set.size();
    	}
  
        return res;
    }
}

Reference

https://leetcode.com/problems/unique-email-addresses/