|
1 | | -package com.cheehwatang.leetcode; |
2 | | - |
3 | | -import java.util.HashSet; |
4 | | -import java.util.Set; |
5 | | - |
6 | | -/** |
7 | | - * Problem: |
8 | | - * Given an array of String 'emails', return the number of different email addresses that can receive emails. |
9 | | - * A valid email address consists of the following: |
10 | | - * 1. A localName (containing only lowercase letters, and may contain '.' or '+'). |
11 | | - * 2. A domainName starting with the '@' symbol. |
12 | | - * |
13 | | - * For the localName, the following rules apply: |
14 | | - * a. Ignore the '.' symbol. |
15 | | - * b. Ignore any letters inclusive and after '+'. |
16 | | - * |
17 | | - * For the domainName, retain every letters. Note that it is guaranteed to have the '.com' suffix. |
18 | | - * |
19 | | - * |
20 | | - * Example 1: |
21 | | - * Input : emails = ["alice@example.com", "alice+bob@example.com", "a.lice+b.ob@example.com"] |
22 | | - * Output : 1 |
23 | | - * Explanation: |
24 | | - * 1. "alice@example.com" = "alice@example.com", no modification made. |
25 | | - * 2. "alice+bob@example.com" = "alice@example.com", the "+bob" is ignored. |
26 | | - * 3. "a.lice+b.ob@example.com" = "alice@example.com", "." in "a.lice" is ignored, as well as "+b.ob" is ignored. |
27 | | - * |
28 | | - * |
29 | | - * Example 2: |
30 | | - * Input : emails = ["a.b@abc.com", "a+b@a.bc.com", "a.b@a.bc.com"] |
31 | | - * Output : 3 |
32 | | - * Explanation: |
33 | | - * 1. "a.b@abc.com" = "ab@abc.com", ignored the "." in the localName. |
34 | | - * 2. "a+b@a.bc.com" = "a@a.bc.com", ignored the "+b" in the localName. |
35 | | - * 3. "a.b@a.bc.com" = "ab@a.bc.com", ignored the "." in the localName only. |
36 | | - * |
37 | | - * |
38 | | - * @author Chee Hwa Tang |
39 | | - */ |
40 | | - |
41 | | -public class UniqueEmailAddresses_HashSet { |
42 | | - |
43 | | - // Approach: |
44 | | - // Split the email by the "@" and "+" symbol, |
45 | | - // then re-assemble the parts before the "+" symbol (while eliminating the "."), |
46 | | - // and the parts inclusive and after the "@" symbol. |
47 | | - |
48 | | - public int numUniqueEmails(String[] emails) { |
49 | | - |
50 | | - // Use set to store adjusted email addresses, as HashSet eliminates duplicates. |
51 | | - Set<String> emailSet = new HashSet<>(); |
52 | | - |
53 | | - // For each email. |
54 | | - for (String email : emails) { |
55 | | - |
56 | | - // Split the email by localName and domainName with .split("@"). |
57 | | - String[] localDomain = email.split("@"); |
58 | | - |
59 | | - // Split the localName by the "+" symbol, so we only take the part before the "+" symbol. |
60 | | - String[] localName = localDomain[0].split("\\+"); |
61 | | - |
62 | | - // For the localName[0], remove the ".". |
63 | | - // Then re-assemble the email address. |
64 | | - String adjustedEmail = localName[0].replace(".", "") + "@" + localDomain[1]; |
65 | | - |
66 | | - // Add the adjustedEmail to the HashSet. If it is a duplicate, it will not be added. |
67 | | - emailSet.add(adjustedEmail); |
68 | | - } |
69 | | - return emailSet.size(); |
70 | | - } |
71 | | -} |
| 1 | +package com.cheehwatang.leetcode; |
| 2 | + |
| 3 | +import java.util.HashSet; |
| 4 | +import java.util.Set; |
| 5 | + |
| 6 | +// Time Complexity : O(n * m), |
| 7 | +// where 'n' is the length of 'emails', and 'm' is the average number of characters per email. |
| 8 | +// For each email, we perform split() and replace() functions which have linear time complexity of O(m). |
| 9 | +// Thus, the time complexity is O(n * m), or linear with the number of characters in 'emails'. |
| 10 | +// |
| 11 | +// Space Complexity : O(n * m), |
| 12 | +// where 'n' is the length of 'emails', and 'm' is the average number of characters per email. |
| 13 | +// The split() method and the string concatenation results in the linear time complexity with the length of each email. |
| 14 | +// Additionally, the HashSet has a linear time complexity, with worst-case being all emails are unique. |
| 15 | + |
| 16 | +public class UniqueEmailAddresses_HashSet { |
| 17 | + |
| 18 | + // Approach: |
| 19 | + // Split the email by the "@" and "+" symbol, |
| 20 | + // then re-assemble the parts before the "+" symbol (while eliminating the "."), |
| 21 | + // and the parts inclusive and after the "@" symbol. |
| 22 | + // Use HashSet to store altered email addresses, and get the number of unique email addresses. |
| 23 | + |
| 24 | + public int numUniqueEmails(String[] emails) { |
| 25 | + |
| 26 | + // Use set to store adjusted email addresses, as HashSet eliminates duplicates. |
| 27 | + Set<String> emailSet = new HashSet<>(); |
| 28 | + |
| 29 | + // For each email. |
| 30 | + for (String email : emails) { |
| 31 | + |
| 32 | + // Split the email by localName and domainName with .split("@"). |
| 33 | + String[] localDomain = email.split("@"); |
| 34 | + |
| 35 | + // Split the localName by the "+" symbol, so we only take the part before the "+" symbol. |
| 36 | + String[] localName = localDomain[0].split("\\+"); |
| 37 | + |
| 38 | + // For the localName[0], remove the ".". |
| 39 | + // Then re-assemble the email address. |
| 40 | + String adjustedEmail = localName[0].replace(".", "") + "@" + localDomain[1]; |
| 41 | + |
| 42 | + // Add the adjustedEmail to the HashSet. If it is a duplicate, it will not be added. |
| 43 | + emailSet.add(adjustedEmail); |
| 44 | + } |
| 45 | + return emailSet.size(); |
| 46 | + } |
| 47 | +} |
0 commit comments