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木」というデータ構造が利用されています.
各言語でのサンプルコード
posted:
last update: