Official

027 - Sign Up Requests (★2) Editorial by kichi2004_


解法

この問題では,各 \(i\) について「文字列 \(S_i\)」が既に存在するかを高速に判定できれば良いです.
Set と呼ばれるデータ構造を使うと,「Set に要素を追加・削除する」「Set に要素が存在するかを判定する」という操作を高速に行うことができます.

Set の実装には「二分探索木 (Binary Search Tree)」や「ハッシュセット」などの実装があります.
追加・削除・存在するかの判定を,前者は \(O(\log N)\) (ただし \(N\) は Set に含まれる要素数),後者は \(O(1)\) で行えます.

実際には,以下のような各言語の標準ライブラリを使用すれば良いです.

言語名 二分探索木 ハッシュセット
C++ std::set std::unordered_set
Python set
C# SortedSet HashSet
Rust BTreeSet(*) HashSet
Java SortedSet HashSet
JavaScript Set
Ruby Set

(*) Rust の BTreeSet は「B木」というデータ構造が利用されています.

各言語でのサンプルコード

C++
Python
C#
Java
Ruby
JavaScript
Nim

posted:
last update: