[Leetcode] 1804. Trie II を実装する

2025年3月28日 / リートコード, テクニカル記事 / によるロクサーヌ

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 ⁴ 通話合計行われます 入れる, 等しい単語をカウント, 開始単語数を数える、そして 消去する.
関数呼び出しは、 消去する、文字列 言葉 トライ内に存在します。

パイソン

				
					クラス 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"))

日本語