跳转至

3860. Unique Email Groups 🔒

题目描述

You are given an array of strings emails, where each string is a valid email address.

Two email addresses belong to the same group if both their normalized local names and normalized domain names are identical.

The normalization rules are as follows:

  • The local name is the part before the '@' symbol.
    • Ignore all dots '.'.
    • Ignore everything after the first '+', if present.
    • Convert to lowercase.
  • The domain name is the part after the '@' symbol.
    • Convert to lowercase.

Return an integer denoting the number of unique email groups after normalization.

 

Example 1:

Input: emails = ["test.email+alex@leetcode.com", "test.e.mail+bob.cathy@leetcode.com", "testemail+david@lee.tcode.com"]

Output: 2

Explanation:

Email Local Normalized Local Domain Normalized Domain Final Email
test.email+alex@leetcode.com test.email+alex testemail leetcode.com leetcode.com testemail@leetcode.com
test.e.mail+bob.cathy@leetcode.com test.e.mail+bob.cathy testemail leetcode.com leetcode.com testemail@leetcode.com
testemail+david@lee.tcode.com testemail+david testemail lee.tcode.com lee.tcode.com testemail@lee.tcode.com

Unique emails are ["testemail@leetcode.com", "testemail@lee.tcode.com"]. Thus, the answer is 2.

Example 2:

Input: emails = ["A@B.com", "a@b.com", "ab+xy@b.com", "a.b@b.com"]

Output: 2

Explanation:

Email Local Normalized Local Domain Normalized Domain Final Email
A@B.com A a B.com b.com a@b.com
a@b.com a a b.com b.com a@b.com
ab+xy@b.com ab+xy ab b.com b.com ab@b.com
a.b@b.com a.b ab b.com b.com ab@b.com

Unique emails are ["a@b.com", "ab@b.com"]. Thus, the answer is 2.

Example 3:

Input: emails = ["a.b+c.d+e@DoMain.com", "ab+xyz@domain.com", "ab@domain.com"]

Output: 1

Explanation:

Email Local Normalized Local Domain Normalized Domain Final Email
a.b+c.d+e@DoMain.com a.b+c.d+e ab DoMain.com domain.com ab@domain.com
ab+xyz@domain.com ab+xyz ab domain.com domain.com ab@domain.com
ab@domain.com ab ab domain.com domain.com ab@domain.com

All emails normalize to "ab@domain.com". Thus, the answer is 1.

 

Constraints:

  • 1 <= emails.length <= 1000
  • 1 <= emails[i].length <= 100
  • emails[i] consists of lowercase and uppercase English letters, digits, and the characters '.', '+', and '@'.
  • Each emails[i] contains exactly one '@' character.
  • All local and domain names are non-empty; local names do not start with '+'.
  • Domain names end with the ".com" suffix and contain at least one character before ".com".

解法

方法一：哈希表

我们可以使用一个哈希表 \(\textit{st}\) 来存储每个邮箱地址的规范化结果。对于每个邮箱地址，我们按照题目要求进行规范化处理：

  • 将邮箱地址分为本地名和域名两部分。
  • 对于本地名，去掉所有的点 .，并且如果存在加号 +，则去掉加号及其后面的部分。最后将本地名转换为小写。
  • 对于域名，将其转换为小写。
  • 将规范化后的本地名和域名拼接起来，得到规范化后的邮箱地址，并将其加入哈希表 \(\textit{st}\) 中。

最后，哈希表 \(\textit{st}\) 中的元素个数即为唯一邮箱组的数量。

时间复杂度 \(O(n \cdot m)\)，其中 \(n\) 和 \(m\) 分别是邮箱地址的数量和每个邮箱地址的平均长度。空间复杂度 \(O(n \cdot m)\)，最坏情况下所有邮箱地址都不同。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def uniqueEmailGroups(self, emails: list[str]) -> int:
        st = set()
        for email in emails:
            local, domain = email.split("@")
            local = local.split("+")[0].replace(".", "").lower()
            domain = domain.lower()
            normalized = local + domain
            st.add(normalized)
        return len(st)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int uniqueEmailGroups(String[] emails) {
        Set<String> st = new HashSet<>();

        for (String email : emails) {
            String[] parts = email.split("@");
            String local = parts[0];
            String domain = parts[1];

            int plusIndex = local.indexOf('+');
            if (plusIndex != -1) {
                local = local.substring(0, plusIndex);
            }

            local = local.replace(".", "").toLowerCase();
            domain = domain.toLowerCase();

            String normalized = local + domain;
            st.add(normalized);
        }

        return st.size();
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    int uniqueEmailGroups(vector<string>& emails) {
        unordered_set<string> st;

        for (auto& email : emails) {
            int atPos = email.find('@');
            string local = email.substr(0, atPos);
            string domain = email.substr(atPos + 1);

            int plusPos = local.find('+');
            if (plusPos != string::npos) {
                local = local.substr(0, plusPos);
            }

            string cleaned;
            for (char c : local) {
                if (c != '.') {
                    cleaned += tolower(c);
                }
            }

            for (char& c : domain) {
                c = tolower(c);
            }

            st.insert(cleaned + domain);
        }

        return st.size();
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
func uniqueEmailGroups(emails []string) int {
    st := make(map[string]struct{})

    for _, email := range emails {
        parts := strings.Split(email, "@")
        local := parts[0]
        domain := parts[1]

        if idx := strings.Index(local, "+"); idx != -1 {
            local = local[:idx]
        }

        local = strings.ReplaceAll(local, ".", "")
        local = strings.ToLower(local)
        domain = strings.ToLower(domain)

        normalized := local + domain
        st[normalized] = struct{}{}
    }

    return len(st)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
function uniqueEmailGroups(emails: string[]): number {
    const st = new Set<string>();

    for (const email of emails) {
        let [local, domain] = email.split('@');
        local = local.split('+')[0].replace(/\./g, '').toLowerCase();
        domain = domain.toLowerCase();

        const normalized = local + domain;
        st.add(normalized);
    }

    return st.size;
}

评论