Guppi StudioPROBLEM 04
同じ受信箱へ届くアドレスを数える
メールアドレスのローカル部を正規化し、実際の受信箱数を求めます。
メールサービスでは、アドレスの @ より前に次の規則があります。
.は配送時に無視される- 最初の
+から@までの文字は無視される @より後のドメインには、どちらの規則も適用しない
numUniqueEmails(emails) は、実際に異なる受信箱へ届くアドレス数を返してください。
例
入力:
["[email protected]", "[email protected]", "[email protected]"]
出力: 2
理由: 先頭2件はどちらも [email protected] へ届く。team.beta は別の受信箱制約
1 <= emails.length <= 20,000- 各アドレスはローカル部、
@、ドメインからなる +と.はローカル部にだけ現れる
対応する問題: LeetCode #929 Unique Email Addresses
この問題の主戦場は「ルールの正確な実装」
計算量で差がつく問題ではなく、仕様を読み違えずに正規化を実装できるかが問われています。面接では「文字列のルール処理を、端の条件まで正しく書けるか」を見る定番の型です。
方針はシンプルです。
全アドレスを「実際に届く形」へ正規化し、異なるものを Set で数える。
ペア同士を比較する O(n²) 構成にする理由はどこにもありません。「同じもの同士を同じ表現に写してから Set / Map で数える」— two-sum や group-anagrams と同じ、HashMap カテゴリの中心パターンです。
解答例
function numUniqueEmails(emails: string[]): number {
const inboxes = new Set<string>();
for (const email of emails) {
const [localPart, domain] = email.split("@");
const local = localPart.split("+")[0].replaceAll(".", "");
inboxes.add(`${local}@${domain}`);
}
return inboxes.size;
}正規化の順序に意味があります。
split("@")— 規則が適用される範囲（ローカル部）を先に切り出すsplit("+")[0]— 最初の+以降を捨てる（+が複数あっても正しい）replaceAll(".", "")— 残った.をすべて削除- ドメインをそのまま連結して戻す
動きを追う — 例の3件
| 入力 | ローカル部 | + 処理後 | . 処理後 | 正規形 |
|---|---|---|---|---|
| [email protected] | team.alpha+news | team.alpha | teamalpha | [email protected] |
| [email protected] | teamalpha | teamalpha | teamalpha | [email protected] |
| [email protected] | team.beta | team.beta | teambeta | [email protected] |
Set に残るのは2種類なので答えは 2 です。
よくある間違い
| 間違い | 何が起きるか |
|---|---|
ドメイン側の . も消す | [email protected] と a@xdev が同一視される。「ドメインは変換しない」ケースで WA |
. の削除を先に、+ の切り捨てを後にする | この問題の規則では結果は同じだが、規則の適用順を意識しない癖がつく。仕様の順で書くのが安全 |
replace(".", "") を使う | JavaScript の replace は文字列指定だと最初の1個しか置換しない。replaceAll か正規表現 /\./g を使う |
split("+") の後に [0] 以外も使う | 2個目以降の + まで残ってしまう |
計算量
総文字数を L として、時間・追加領域とも O(L) です。各アドレスを一度ずつ読む以上のことはしていません。
面接でどう話すか
「各アドレスを配送先の正規形に変換して、Set で種類数を数えます。変換はローカル部だけに適用するので、先に
@で分けてから、最初の+以降を捨て、ドットを全部消します。エッジケースとして、ドメイン側は触らないこと、replaceは最初の1個しか消さないのでreplaceAllを使うことに注意します。」
ルール系の問題では、書き始める前に例を1件手で正規化して見せ、規則の理解を面接官と合わせるのが効果的です。認識ズレによる手戻りがなくなり、仕様確認の習慣もアピールできます。
STEPWISE HINTS
ヒント
01最初の一手
各アドレスを同じ規則で正規化してから、異なる値の個数を数えます。
02処理の組み立て
@ より前だけを加工します。最初の + 以降を捨て、残った . を削除します。ドメイン側は変えません。
03コードの形
email を @ で分ける。local = local.split('+')[0].replaceAll('.', '')。local + '@' + domain を Set に追加し、size を返す。
AFTER ACCEPTED
解説
まずは自分の言葉で方針を説明し、コードに落としてみましょう。