Skip to content

Instantly share code, notes, and snippets.

@davidrft
Created February 6, 2020 11:55
Show Gist options
  • Save davidrft/535c5d026bfe8b9d1422db3a5ce01439 to your computer and use it in GitHub Desktop.
Save davidrft/535c5d026bfe8b9d1422db3a5ce01439 to your computer and use it in GitHub Desktop.
A wildcard trie implementation as seen is riff.ie/posts/wildcard-searching-trie
from typing import Dict, List, Any
WILDCARD = '?'
class Trie:
def __init__(self) -> None:
self.children: Dict[str: Trie] = {}
self.isLeaf: bool = False
def insert(self, key: str) -> None:
node = self
for char in key:
if char not in node.children:
node.children[char] = Trie()
node = node.children[char]
node.isLeaf = True
def find(self, key: str) -> List[str]:
stack = [(self, 0, '')]
result = []
while stack:
curr, count, currWord = stack.pop()
if count == len(key):
if curr.isLeaf: result.append(currWord)
continue
currChar = key[count]
if currChar == WILDCARD:
for childChar, node in curr.children.items():
stack.append((node, count + 1, currWord + childChar))
continue
if currChar in curr.children:
node = curr.children[currChar]
stack.append((node, count + 1, currWord + currChar))
return result
def main():
trie = Trie()
trie.insert('word')
trie.insert('ward')
trie.insert('oi')
trie.insert('boi')
assert(trie.find('??') == ['oi'])
assert(trie.find('') == [])
assert(trie.find('w?rd') == ['ward', 'word'])
assert(trie.find('???') == ['boi'])
assert(trie.find('?oi') == ['boi'])
if __name__ == '__main__':
main()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment