[Leetcode] 0211. 単語の追加と検索のデータ構造の設計

/ リートコード, テクニカル記事 / による

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

中くらい

新しい単語の追加と、文字列が以前に追加された文字列と一致するかどうかの検索をサポートするデータ構造を設計します。

実装する 単語辞書 クラス：

  • 単語辞書() オブジェクトを初期化します。
  • void addWord(単語) 追加 言葉 データ構造に合わせると、後で一致させることができます。
  • bool 検索(単語) 返品 真実 データ構造内に一致する文字列がある場合 言葉 または 間違い さもないと。 言葉 ドットが含まれる場合があります '.' ドットは任意の文字と一致できます。

 

例：

入力
["WordDictionary","addWord","addWord","addWord","search","search","search","search"] [[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
出力
[null、null、null、null、偽、真、真、真]

説明
WordDictionary wordDictionary = 新しい WordDictionary(); wordDictionary.addWord("悪い"); wordDictionary.addWord("お父さん"); wordDictionary.addWord("mad"); wordDictionary.search("pad"); // False を返す wordDictionary.search("bad"); // True を返す wordDictionary.search(".ad"); // True を返す wordDictionary.search("b.."); // Trueを返す

 

制約:

  • 1 <= 単語の長さ <= 25
  • 言葉 で 追加ワード 小文字の英語の文字で構成されています。
  • 言葉 で 検索 構成する '.' または小文字の英語の文字。
  • 最大で 2 点々 言葉 のために 検索 クエリ。
  • せいぜい 10 4 電話がかかってくる 追加ワード そして 検索.

パイソン

				
					# 時間計算量: O(M) # 空間計算量: O(M) クラス TrieNode: def __init__(self): self.children = {} self.isEnd = False クラス WordDictionary: def __init__(self): self.root = TrieNode() self.maxLen = 0 def addWord(self, word: str) -> None: node = self.root l = 0 for char in word: if char not in node.children: node.children[char] = TrieNode() node = node.children[char] l += 1 self.maxLen = max(self.maxLen, l) node.isEnd = True def search(self, word: str) -> bool: if len(word) > self.maxLen: return False def helper(idx, node): for i in range(idx, len(word)): if word[i] == ".": for child in node.children.values(): if helper(i + 1, child): return True return False else: if word[i] not in node.children: return False node = node.children[word[i]] return node.isEnd return helper(0, self.root) wordDictionary = WordDictionary() wordDictionary.addWord("bad") wordDictionary.addWord("dad") wordDictionary.addWord("mad") print(wordDictionary.search("pad")) print(wordDictionary.search("bad")) print(wordDictionary.search(".ad")) print(wordDictionary.search("b.."))

関連記事