この記事では、LeetCode 1804 Implement Trie II の解答を、問題解決のアプローチやアルゴリズムの手順から時間計算量や空間計算量まで、完全に解説します。また、境界ケースをまとめ、3 つの解答を比較することで、Implement Trie II を一度に理解できるようにサポートします。
Python、C++、JavaScript、SQL、TypeScript の多様な LeetCode ソリューションを探索してください。面接の準備、学習、複数のプログラミング言語でのコードの練習に最適です。 Github リポジトリ リンク
あ トライ (「トライ」と発音)または プレフィックスツリー 文字列のデータセット内のキーを効率的に保存および取得するために使用されるツリー データ構造です。このデータ構造には、オートコンプリートやスペルチェッカーなど、さまざまな用途があります。
Trie クラスを実装します。
トライ()トライオブジェクトを初期化します。void 挿入(文字列単語)文字列を挿入します言葉トライに。int countWordsEqualTo(文字列単語)文字列のインスタンス数を返します言葉トライで。int countWordsStartingWith(文字列プレフィックス)文字列を含むトライ内の文字列の数を返します。接頭辞接頭辞として。void 消去(文字列単語)文字列を消去します言葉トライから。
例 1:
入力
["Trie", "insert", "insert", "countWordsEqualTo", "countWordsStartingWith", "erase", "countWordsEqualTo", "countWordsStartingWith", "erase", "countWordsStartingWith"] [[], ["apple"], ["apple"], ["apple"], ["apple"], ["apple"], ["apple"], ["app"]]
出力
[null、null、null、2、2、null、1、1、null、0]
説明
トライ trie = new Trie(); trie.insert("リンゴ"); // 「apple」を挿入します。 trie.insert("リンゴ"); // 別の「リンゴ」を挿入します。 trie.countWordsEqualTo("リンゴ"); // "apple" のインスタンスが 2 つあるので、2 を返します。trie.countWordsStartingWith("app"); // "app" は "apple" のプレフィックスなので 2 を返します。trie.erase("apple"); // 1 つの「リンゴ」を消去します。 trie.countWordsEqualTo("リンゴ"); // 現在、「apple」のインスタンスは 1 つだけなので、1 を返します。trie.countWordsStartingWith("app"); // 1 を返す trie.erase("apple"); // 「apple」を消去します。これでトライは空になりました。 trie.countWordsStartingWith("アプリ"); // 0 を返す
制約:
1 <= 単語の長さ、接頭辞の長さ <= 2000言葉そして接頭辞小文字の英語のみで構成されます。- せいぜい
3 * 10 4通話 合計 行われます入れる,等しい単語をカウント,開始単語数を数える、 そして消去する. - 関数呼び出しは、
消去する、文字列言葉トライ内に存在します。
パイソン
クラス TrieNode: def __init__(self): self.links = [None] * 26 self.wordsEndingHere = 0 self.wordsStartingHere = 0 クラス Trie: def __init__(self): self.root = TrieNode() def insert(self, word: str) -> None: node = self.root for w in word: charIndex = ord(w) - ord('a') if not node.links[charIndex]: node.links[charIndex] = TrieNode() node = node.links[charIndex] node.wordsStartingHere += 1 node.wordsEndingHere += 1 def countWordsEqualTo(self, word: str) -> int: node = self.root for w in word: charIndex = ord(w) - ord('a') if not node.links[charIndex]: return 0 node = Trie オブジェクトは次のようにインスタンス化され、呼び出されます: trie = Trie() trie.insert("apple") trie.insert("apple") print(trie.countWordsEqualTo("apple")) print(trie.countWordsStartingWith("app")) trie.erase("apple") print(trie.countWordsEqualTo("apple")) print(trie.countWordsStartingWith("app")) trie.erase("apple") print(trie.countWordsStartingWith("app"))
LeetCode問題拡張演習
同じシリーズの他の問題解決ノートも練習用としてお勧めします。
さらに詳しく知りたい方はこちらをご覧ください
Trie II問題解決アプローチの実装
基本バージョンと比較して、このバージョンでは「同じ単語の複数回挿入」と「削除」をサポートする必要があるため、フラグだけでは不十分であり、カウンターに置き換える必要があります。各ノードは、countPrefix(ここを通過する単語の数)とcountWord(ここで終了する単語の数)を記録します。削除時には、パスに沿ってカウントを減らすだけでよく、実際にノードを解放する必要はありません。
Trie IIアルゴリズムを実装する手順
- このノードには、countPrefix と countWord という 2 つの整数が格納されるはずです。
- 挿入: パス上の各ノードに対して CountPrefix++ を、最終ノードに対して CountWord++ を挿入します。
- countWordsEqualTo: 終点に達した場合は countWord を返します。途中で停止した場合は 0 を返します。
- erase: countPrefix – パス上の各ノードについて、countWord – 終点について。countWordsStartingWith は終点の countPrefix を返します。
トライ木IIの複雑性分析の実装
| プロジェクト | 複雑 |
|---|---|
| 時間計算量 | O(L) |
| 空間の複雑さ | O(N·L) |
これら4つの操作はすべてLステップの単一パスをたどり、時間計算量はO(L)です。空間計算量は基本バージョンと同じO(N・L)ですが、各ノードには2つの追加の整数が格納されます。フラグの代わりにカウンタを使用することで、削除はコストのかかるノードの再利用操作ではなく、O(L)の減算操作になります。
Trie IIの実装における境界ケースとよくあるエラー
- この問題では、消去操作は既存の単語のみを呼び出すことが保証されています。そうでない場合、カウントは負の値になります。
- countPrefixフィールドとcountWordフィールドは同じフィールドを共有することはできません。接頭辞のカウントは、単語のカウント以上でなければなりません。
- 同じ単語を繰り返し挿入する場合、countWord は 1 に設定するのではなく、インクリメントされるべきです。
- カウントがゼロになった場合でもノードは保持されるため、実装が最も簡単で、正当性にも影響しません。
Implement Trie II の他のソリューションとの比較
| 解法 | 時間 | 空間 | 例示する |
|---|---|---|---|
| ハッシュテーブルは、単語が出現した回数を記録します。 | O(1)クエリ / O(N)プレフィックス | O(N·L) | 接頭辞統計情報を取得するには、テーブル全体をスキャンする必要があります。 |
| 基本トライ木+外部計数テーブル | O(L) | O(N·L) | 2つのデータセットを同期させる作業は、エラーが発生しやすい。 |
| Nodeにはデュアルカウンターが内蔵されています | O(L) | O(N·L) | この記事では |
