Design Add and Search Words Data Structure
2つの操作を持つ単語辞書を作成します。addWord wは単語wを保存します。search pは、保存された単語の中にパターンpに一致するものがあるかどうかを判定します。一致するには長さが同じで、各位置でパターンが同じ文字または任意の1文字を表すドット.である必要があります。
操作iは、単語またはパターンwords[i]に対するops[i]です。空の辞書に対して順番に実行し、それぞれについて1つの文字列を返します。addWordには"null"、searchには"true"または"false"を返します。
関数
- opsstring-array
- 操作が実行される順序
- wordsstring-array
- 追加する単語または検索するパターン。1回の操作につき1つ。
- 戻り値string-array
- 操作ごとに1つの回答をテキストとして
制約
1 ≤ ops.length ≤ 2500words.length == ops.length- すべての
ops[i]はaddWordまたはsearchです。 1 ≤ words[i].length ≤ 20- 追加する単語には、小文字の英字のみが含まれます。
- 検索するパターンには、小文字の英字と最大3個のドットが含まれます。
例
- 入力
- ops = ["addWord", "addWord", "search", "search", "search", "search"]words = ["rose", "rise", "r.se", "ros", "rose.", "..s."]
- 出力
- ["null", "null", "true", "false", "false", "true"]
- 説明
r.seは両方の単語に一致します。ドットはroseの o とriseの i に対応します。ドットは欠けている文字を表すことはないため、rosとrose.は一致しません。両方の単語で s が3文字目なので、..s.は一致します。
- 入力
- ops = ["search", "addWord", "search", "search", "search"]words = ["...", "sky", "...", "s.y", "sk"]
- 出力
- ["false", "null", "true", "true", "false"]
- 説明
- 辞書は空の状態から始まるため、
...は何も見つけません。skyを追加すると、...とs.yの両方が一致しますが、skは短すぎます。
- 入力
- ops = ["addWord", "addWord", "search", "search", "search"]words = ["maple", "mango", "ma..o", "m...y", "m.p.e"]
- 出力
- ["null", "null", "true", "false", "true"]
- 説明
ma..oの最初のドットは、mapleの p またはmangoの n にできます。mapleは e で終わりますが、mangoは条件に合います。y で終わる単語はないため、m...yは一致せず、m.p.eはmapleに一致します。
発展問題
パターンに、空文字も含む任意の文字列を表す*も含められるとしたら、searchをどのように拡張しますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
ドットがなければ、保存された単語のハッシュセットを使って、各検索に1回の参照で答えられます。ドットがあると、そうはいきません。
c.tはcat、cot、またはcutの可能性があります。単語を1文字ずつたどり、次に来る可能性のある文字をすべて確認できるデータ構造は何でしょうか？単語をトライに格納し、格納された単語の末尾となる各ノードにフラグを付けます。パターン内の文字は1つの子リンクをたどります。ドットは任意の文字を表すため、現在のノードの各子を試し、分岐が行き止まりになったら戻ります。
再帰的な
match(node, i)を書きましょう。パターンの末尾では、ノードの終了フラグを返します。文字の場合は、その子ノードをたどり、存在しなければ失敗します。ドットの場合は、いずれかの子ノードでmatch(child, i+1)が成功した時点で true を返し、どの子ノードでも成功しなければ false を返します。
解説
ドットは、検索で探したい単語を指定できないことを意味します。ma..o は676個の候補語を表し、保存されている単語だけが対象になります。トライ木では、同じ文字で始まる単語は1つの経路を共有します。パターン内の文字は1つのリンクをたどり、ドットは存在する子ノードだけに分岐し、深さ優先探索は行き止まりの枝から戻ります。
パターンを保存されているすべての単語と比較する
考え方
追加された単語をリストに保存し、それぞれをパターンと照合します。長さが同じで、各位置にドットまたは同じ文字があることが条件です。これが一致の定義であり、保存されたすべての単語と照合するため、答えは正確です。
検索のたびにリスト全体を調べるため、最大 L 文字の単語が n 個ある場合、ドットのないパターンでも計算量は O(n·L) です。1,250 回追加してから1,250 回検索すると、1,250 × 1,250 = 1,562,500 個の単語を調べます。
アルゴリズム
- 追加した単語をリストに保持します。
addWord wの場合、wを追加し、"null"を記録します。 search pの場合、同じ長さの各単語とpを位置ごとに比較し、ドットは任意の文字に一致するものとします。- 最初に一致した場合は
"true"を記録し、一致しない場合は"false"を記録します。
def matches(pattern, word):
# Same length, and every position holds a dot or the same letter.
if len(pattern) != len(word):
return False
for p, w in zip(pattern, word):
if p != "." and p != w:
return False
return True
def wordDictionaryOps(ops, words):
stored = []
result = []
for op, word in zip(ops, words):
if op == "addWord":
stored.append(word)
result.append("null")
else:
found = any(matches(word, s) for s in stored)
result.append("true" if found else "false")
return resultドットに対する深さ優先探索を使ったトライ
考え方
単語をトライに格納します。roseとriseはrノードを共有し、その後oとiに分岐します。終端フラグは、格納された単語が終わる各ノードに付けます。文字のパターンは、トライを下っていく1つの経路です。ドットは任意の文字を表すため、ドットに来たら既存の子ノードをすべて試し、そのうち1つが一致につながった時点でtrueを返します。
ma..oの場合、maのノードにはpとnの子ノードがあります。pをたどると、2つ目のドットはlに進みますが、そこにはoの子ノードがないため、検索は戻ってnを試します。g、次にoへ進み、そこでmangoが終わります。
一致するには、終端フラグの付いたノードでパターン全体を使い切る必要があります。これにより長さも判定できます。rosは終端フラグのないノードで止まり、rose.は進むリンクがなくなります。ドット1つで最大26個の分岐を調べるため、ドットがd個ある場合、訪れるノード数は最大26^d · Lです。また、ドットを含まないパターンの計算量はO(L)です。
アルゴリズム
- 各ノードには子ノードへのリンクと終了フラグがあり、最初はオフです。
addWord wの場合：ルートからwをたどり、存在しないノードを作成して、たどり終えた位置で終了フラグを設定します。match(node, i)：iがパターンの長さに達したら、そのノードの終了フラグを返します。p[i]が文字なら、子ノードが存在しない場合はfalseを返し、それ以外の場合はmatch(child, i+1)を返します。ドットの場合は、既存の子ノードのいずれかについてmatch(child, i+1)が成功すればtrueを返し、それ以外の場合はfalseを返します。- 検索ごとに
match(root, 0)を記録し、追加ごとに"null"を記録します。
class TrieNode:
def __init__(self):
self.children = {} # letter -> TrieNode
self.is_end = False # does a stored word end at this node?
class WordDictionary:
def __init__(self):
self.root = TrieNode()
def add_word(self, word):
node = self.root
for ch in word:
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
node.is_end = True
def search(self, pattern):
return self._match(self.root, pattern, 0)
def _match(self, node, pattern, i):
# Can the path below node spell pattern[i:] and end on a stored word?
if i == len(pattern):
return node.is_end
ch = pattern[i]
if ch == ".":
# A dot stands for any letter: try each child until one works.
for child in node.children.values():
if self._match(child, pattern, i + 1):
return True
return False
child = node.children.get(ch)
return child is not None and self._match(child, pattern, i + 1)
def wordDictionaryOps(ops, words):
dictionary = WordDictionary()
result = []
for op, word in zip(ops, words):
if op == "addWord":
dictionary.add_word(word)
result.append("null")
else:
result.append("true" if dictionary.search(word) else "false")
return result
落とし穴と境界ケース
- 最初の子ノードだけでドットの判定を決めてしまう。
ma..oではpの分岐は失敗し、nの分岐は成功するため、最初にpを試すコードで最初の子ノードの結果を返すと、falseになってしまう。すべての子ノードが失敗した場合にのみfalseを返す。 - どのノードでもパターンが尽きたらtrueを返してしまう。
roseを追加すると、rosはノードに到達するが、そこでは単語が終わっていない。終端フラグを確認する。 - ドットが存在しない文字にも一致してしまう。
card.はcardsには一致するが、cardには一致しない。 - ドットを文字として扱ってしまう。
'.' - 'a'で26要素の配列をインデックス指定すると配列の範囲外を参照するため、まずドットかどうかを判定する。
よくある質問3
単語の追加と検索の時間計算量はどれくらいですか？
長さLの単語の追加にはO(L)かかり、ドットを含まない検索も、保存されている単語数にかかわらず同様です。d個のドットを含む検索は、最悪の場合O(26^d · L)かかります。T個の文字を追加した場合、メモリ使用量はO(T)個のノードです。
トライではなくハッシュセットを使って解けますか？
はい、ただしトレードオフがあります。集合を使えば、ドットのないパターンには1回の検索で答えられます。ドットがある場合は、その長さの保存済み単語をすべて調べる（O(n·L)）か、各ドットに26文字すべてを当てはめて、それぞれの結果を検索する必要があります。ドットが3つなら、検索は17,576回です。
トライの検索は再帰的に行うべきですか、それとも反復的に行うべきですか？
どちらでも構いません。再帰はパターンの文字ごとに1レベル進み、ここでは最大20レベルなので、呼び出しスタックは小さいままです。反復版では (node, position) のペアのスタックを保持し、ドットごとにすべての子をプッシュします。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def wordDictionaryOps(ops, words):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
ops = ["addWord", "addWord", "search", "search", "search", "search"] words = ["rose", "rise", "r.se", "ros", "rose.", "..s."]
期待される出力
["null", "null", "true", "false", "false", "true"]