Unique Email Addresses
Easy
Every email consists of a local name and a domain name, separated by the @ sign.
For example, inalice@leetcode.com
, alice
is the local name, andleetcode.com
is the domain name.
Besides lowercase letters, these emails may contain'.'
s or'+'
s.
If you add periods ('.'
) between some characters in thelocal namepart 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.)
If you add a plus ('+'
) in thelocal 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.)
It is possible to use both of these rules at the same time.
Given a list ofemails
, we send one email to each address in the list. How many different addresses actually receive mails?
Example 1:
Input:
["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
Note:
1 <= emails[i].length <= 100
1 <= emails.length <= 100
Each
emails[i]
contains exactly one'@'
character.
Analysis
基本思想就是将email都转化为统一的形式canonical form,即去掉'.', '+等字符的影响,最后返回unique元素hashset的大小即可。
Solution
LeetCode official - Using indexOf(), replaceAll() - (39 ms, faster than 34.09%)
class Solution {
public int numUniqueEmails(String[] emails) {
Set<String> seen = new HashSet();
for (String email: emails) {
int i = email.indexOf('@');
String local = email.substring(0, i);
String rest = email.substring(i);
if (local.contains("+")) {
local = local.substring(0, local.indexOf('+'));
}
local = local.replaceAll(".", "");
seen.add(local + rest);
}
return seen.size();
}
}
Character by character, StringBuilder - (25 ms, faster than 72.51%)
class Solution {
public int numUniqueEmails(String[] emails) {
if (emails == null) {
return 0;
}
HashSet<String> set = new HashSet<>();
for (String email : emails) {
set.add(convertEmailAddress(email));
}
return set.size();
}
private String convertEmailAddress(String email) {
StringBuilder sb = new StringBuilder();
int i = 0;
boolean beforeAtSign = true;
while (i < email.length()) {
if (email.charAt(i) == '@') {
i++;
beforeAtSign = false;
} else if (beforeAtSign && email.charAt(i) == '.') {
i++;
} else if (beforeAtSign && email.charAt(i) == '+') {
while (i < email.length()) {
i++;
if (email.charAt(i) == '@') {
beforeAtSign = false;
break;
}
}
}
sb.append(email.charAt(i));
i++;
}
return sb.toString();
}
}
(Preferred*) Another Character by character implementation by @FLAGbigoffer- (17ms, 89.80%)
We can do
BETTER
without usingreplace()
. Actually in some situations, we even don't need scan the entire email address. Consider this case:
a+nadgkj.ansjfnakjn.gaskjgb.ubeijbg.kjncna.oskenijb.golkn.asignoaeroib.gjoibv.oanod.safa.e.f.asdf.sa.df.a@g.com
. What we do here is to scan the email address until meeting the first
'+'
sign. Then scan reversely to find the'@'
sign.
class Solution {
public int numUniqueEmails(String[] emails) {
Set<String> emailsSet = new HashSet<>();
for (String e : emails) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < e.length(); i++) {
if (e.charAt(i) == '.') {
continue;
} else if (e.charAt(i) == '+') {
int idx = e.length() - 1;
while (e.charAt(idx) != '@') {
idx--;
}
sb.append(e.substring(idx));
break;
} else {
sb.append(e.charAt(i));
}
}
emailsSet.add(sb.toString());
}
return emailsSet.size();
}
}
Reference
https://leetcode.com/problems/unique-email-addresses/solution/
https://leetcode.com/problems/unique-email-addresses/discuss/186798/Java-7-liner-with-comment.
Last updated
Was this helpful?