Trie II 問題解決チュートリアルの実装:3つのソリューションの完全比較 | LeetCode 1804 ベストプラクティス

トライ木IIの実装問題解決チュートリアル図 | LeetCode 1804

この記事では、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"))
				
			

Trie II問題解決アプローチの実装

基本バージョンと比較して、このバージョンでは「同じ単語の複数回挿入」と「削除」をサポートする必要があるため、フラグだけでは不十分であり、カウンターに置き換える必要があります。各ノードは、countPrefix(ここを通過する単語の数)とcountWord(ここで終了する単語の数)を記録します。削除時には、パスに沿ってカウントを減らすだけでよく、実際にノードを解放する必要はありません。

Trie IIアルゴリズムを実装する手順

  1. このノードには、countPrefix と countWord という 2 つの整数が格納されるはずです。
  2. 挿入: パス上の各ノードに対して CountPrefix++ を、最終ノードに対して CountWord++ を挿入します。
  3. countWordsEqualTo: 終点に達した場合は countWord を返します。途中で停止した場合は 0 を返します。
  4. 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)この記事では