Prefix tree for fast prefix queries, dictionary word search, and bitwise tricks
Store characters/bits along paths to share common prefixes and support fast prefix checks.
Use for autocomplete, word search, and maximum XOR of pairs using bitwise trie.
Standard char trie
class TrieNode:
def __init__(self): self.children = {}; self.end=False
class Trie:
def __init__(self): self.root=TrieNode()
def insert(self, word):
node=self.root
for ch in word: node=node.children.setdefault(ch, TrieNode())
node.end=True
def search(self, word):
node=self.root
for ch in word:
if ch not in node.children: return False
node=node.children[ch]
return node.end
def startsWith(self, prefix):
node=self.root
for ch in prefix:
if ch not in node.children: return False
node=node.children[ch]
return TruePrefix traversal to collect words
def autocomplete(trie, prefix):
# trie: instance of Trie above
def node_for(prefix):
n = trie.root
for ch in prefix:
if ch not in n.children: return None
n = n.children[ch]
return n
def dfs(node, path, out):
if node.end: out.append(''.join(path))
for ch, nxt in node.children.items():
path.append(ch); dfs(nxt, path, out); path.pop()
node = node_for(prefix)
res = []
if node: dfs(node, list(prefix), res)
return resTrie over bits for max XOR
# Simple bitwise trie using dicts for max XOR query
class BitTrie:
def __init__(self): self.root={}
def insert(self, num):
n=self.root
for i in range(31,-1,-1):
b=(num>>i)&1
if b not in n: n[b]={}
n=n[b]
def max_xor(self, num):
n=self.root; ans=0
for i in range(31,-1,-1):
b=(num>>i)&1; t=1-b
if t in n: ans|=(1<<i); n=n[t]
else: n=n.get(b, {})
return ansdef template(*args, **kwargs):
# General template placeholder
passL is word length.
Nodes per unique prefix.