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.
Insert/search/startsWith over node maps with end flags; bitwise trie variant stores bits for max-XOR queries.
# Trie Template
class TrieNode:
def __init__(self):
self.children = {}
self.end = False
class Trie:
def __init__(self): self.root=TrieNode()
def insert(self, word):
cur=self.root
for ch in word:
if ch not in cur.children: cur.children[ch]=TrieNode()
cur=cur.children[ch]
cur.end=True
def search(self, word):
cur=self.root
for ch in word:
if ch not in cur.children: return False
cur=cur.children[ch]
return cur.end
def startsWith(self, pref):
cur=self.root
for ch in pref:
if ch not in cur.children: return False
cur=cur.children[ch]
return TrueStandard 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 ansL is word length.
Nodes per unique prefix.