🖋

LeetCode 929. Unique Email Addresses (Python3)

に公開
Python
LeetCode
tech

はじめに

LeetCode 「929. Unique Email Addresses」の問題を Python3 で解きました。

問題

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

問題文

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 emails[i], return the number of different addresses that actually receive mails.

和訳
有効なメールアドレスはすべて、ローカル名とドメイン名で構成され、これらは「@」記号で区切られます。小文字のアルファベットに加え、メールアドレスには1つ以上の「.」または「+」が含まれる場合があります。

例えば、「alice@leetcode.com」では、「alice」がローカル名、「leetcode.com」がドメイン名です。
ローカル名部分にピリオド '.' を追加すると、そのアドレス宛てのメールはピリオドなしのローカル名と同じアドレスに転送されます。このルールはドメイン名には適用されません。

例：「alice.z@leetcode.com」と「alicez@leetcode.com」は同じメールアドレスに転送されます。
ローカル名にプラス記号 '+' を追加すると、最初のプラス記号以降の文字列はすべて無視されます。これにより特定のメールをフィルタリングできます。このルールはドメイン名には適用されません。

例として、「m.y+name@email.com」は「my@email.com」に転送されます。
これらのルールは同時に使用可能です。

メール送信先として指定された文字列配列 emails に対し、各 emails[i] 宛に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.

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

制約

  • 1 <= emails.length <= 100
  • 1 <= emails[i].length <= 100
  • emails[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.
  • Domain names end with the ".com" suffix.
  • Domain names must contain at least one character before ".com" suffix.

解答1

メールアドレスのリストから、実際に送信される数を求める問題です。
ローカル部のルールに従い正規化を行って、重複を排除した数が求めたい数です。

正規化に関しては以下を行います：

  • .は無視する
  • +以降は無視する

各メールを正規化してから集合(set)に追加することで重複は自動で消えるので、最後に集合の大きさを返します。

コード

class Solution:
    def numUniqueEmails(self, emails: List[str]) -> int:
        email_set = set()
        for email in emails:
            local, domain = email.split("@", 1)
            local = local.split("+", 1)[0].replace(".", "")
            email_set.add(local + "@" + domain)
        return len(email_set)

local.split('+', 1)[0]で最初の+以降を取らないようにしています。
replace(".", "")で.を除去しています。

計算量

  • 時間的計算量：O(n * L)
    • nはメールの数
    • Lは各メールの文字列長
      • 各メールの操作はO(L)
  • 空間的計算量：O(n * L)
    • 正規化アドレスを格納する集合
GitHubで編集を提案

Discussion