トライ木-ワイルドカードついて
概要
- トライ木の探索において、
"."などの正規表現を使用できるように拡張したもの "."が指定された時、どんな単語でも次のnodeに移行できるように許可するように記述する
実装例
class TrieNode(object):
def __init__(self, char: str):
self.char = char
self.children = dict()
self.counter = 0
class Trie:
def __init__(self):
self.root = TrieNode("")
def addWord(self, word: str) -> None:
node = self.root
for char in word:
if char in node.children:
node = node.children[char]
else:
new_node = TrieNode(char)
node.children[char] = new_node
node = new_node
# 何回単語が挿入されたかを検知する
node.counter += 1
def search(self, word: str) -> bool:
node = self.root
chars = list(word)
def _search(node, chars, idx):
if len(chars) == idx:
return node.counter > 0
char = chars[idx]
if char == ".":
rets = []
for next_node in node.children.values():
ret = _search(next_node, chars, idx+1)
rets.append(ret)
return any(rets)
elif char in node.children:
next_node = node.children[char]
return _search(next_node, chars, idx+1)
else:
return False
return _search(node, chars, 0)
trie = Trie()
trie.addWord("bad")
trie.addWord("dad")
trie.addWord("mad")
assert(trie.search("pad") == False)
assert(trie.search("bad") == True)
assert(trie.search(".ad") == True)
assert(trie.search("b..") == True)