[Leetcode] 0208. Trie を実装する

Python、C++、JavaScript、SQL、TypeScript の多様な LeetCode ソリューションを探索してください。面接の準備、学習、複数のプログラミング言語でのコードの練習に最適です。 Github リポジトリリンク

あ トライ （「トライ」と発音）または プレフィックスツリー 文字列のデータセット内のキーを効率的に保存および取得するために使用されるツリーデータ構造です。このデータ構造には、オートコンプリートやスペルチェッカーなど、さまざまな用途があります。

Trie クラスを実装します。

トライ() トライオブジェクトを初期化します。
void 挿入(文字列単語) 文字列を挿入します 言葉 トライに。
ブール検索(文字列単語) 返品 真実 文字列 言葉 トライ内にある（つまり、以前に挿入された）、そして 間違い さもないと。
ブール型 startsWith(文字列プレフィックス) 返品 真実 以前に挿入された文字列がある場合 言葉 接頭辞を持つ 接頭辞、そして 間違い さもないと。

例 1:

入力
["Trie", "insert", "search", "search", "startsWith", "insert", "search"] [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
出力
[null、null、true、false、true、null、true]

説明
トライ trie = new Trie(); trie.insert("リンゴ"); trie.search("リンゴ"); // True を返す trie.search("app"); // False を返す trie.startsWith("app"); // True を返す trie.insert("app"); trie.search("アプリ"); // Trueを返す

制約:

1 <= 単語の長さ、接頭辞の長さ <= 2000
言葉 そして 接頭辞 小文字の英語のみで構成されます。
せいぜい 3 * 10 ⁴ 通話合計行われます 入れる, 検索、そして 開始.

パイソン

				
					# insert() # 時間計算量: O(l) # 空間計算量: O(l) # search() # 時間計算量: O(l) # 空間計算量: O(1) # search prefix() # 時間計算量: O(l) # 空間計算量: O(1) クラス TrieNode: def __init__(self, char: str = ""): self.char = char self.children = {} self.isEnd = False クラス Trie: def __init__(self): self.root = TrieNode() def insert(self, word: str): node = self.root for c in word: if c in node.children: node = node.children[c] else: newNode = TrieNode() node.children[c] = newNode node = newNode node.isEnd = True def search(self, word: str): node = self.root for c in word: if c not in node.children: return False node = node.children[c] return node.isEnd def startsWith(self, prefix: str): node = self.root for c in prefix: if c not in node.children: return False node = node.children[c] return True # Trie オブジェクトは次のようにインスタンス化され、呼び出されます: trie = Trie() trie.insert("apple") print(trie.search("apple")) print(trie.search("app")) print(trie.startsWith("app")) trie.insert("app") print(trie.search("app"))

パイソン

関連記事