🌲 Tries & Bit Manipulation
Tries answer prefix questions in O(word length); bit tricks turn pairs, parity and subsets into O(1) integer ops.
Recognize the pattern
Many words + "starts with" / autocomplete queries → trie
Find many dictionary words on a letter grid → trie + grid DFS, stop when not a prefix
Pattern search where "." matches any letter → trie + DFS that branches on "."
Maximise a XOR over pairs → binary trie, greedy from the highest bit
Every element appears twice except one → XOR everything together
Count set bits / test power of two → x & (x - 1) drops the lowest 1
Try every subset of ≤ ~20 items → loop mask over range(1 << n)
Trie (class version)
class TrieNode:
def __init__(self):
self.children: dict[str, "TrieNode"] = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word: str) -> None:
node = self.root
for ch in word:
node = node.children.setdefault(ch, TrieNode())
node.is_end = True
def _walk(self, s: str) -> "TrieNode | None":
node = self.root
for ch in s:
node = node.children.get(ch)
if node is None:
return None
return node
def search(self, word: str) -> bool:
node = self._walk(word)
return node is not None and node.is_end
def starts_with(self, prefix: str) -> bool:
return self._walk(prefix) is not None
Trie (nested dicts) + wildcard DFS
END = "$"
def insert(root: dict, word: str) -> None:
node = root
for ch in word:
node = node.setdefault(ch, {})
node[END] = True
def match(node: dict, word: str, i: int = 0) -> bool:
if i == len(word):
return END in node
if word[i] == ".":
return any(match(child, word, i + 1)
for k, child in node.items()
if k != END)
child = node.get(word[i])
return child is not None and match(child, word, i + 1)
Words on a board (trie + grid DFS)
def find_words(board: list[list[str]],
words: list[str]) -> list[str]:
root: dict = {}
for w in words:
node = root
for ch in w:
node = node.setdefault(ch, {})
node["$"] = w # store the word
rows, cols = len(board), len(board[0])
found: list[str] = []
def dfs(r: int, c: int, parent: dict) -> None:
ch = board[r][c]
node = parent[ch]
if "$" in node:
found.append(node.pop("$")) # no dupes
board[r][c] = "#" # visited
for nr, nc in ((r+1, c), (r-1, c),
(r, c+1), (r, c-1)):
if (0 <= nr < rows and 0 <= nc < cols
and board[nr][nc] in node):
dfs(nr, nc, node)
board[r][c] = ch # restore
if not node: # prune dead branch
parent.pop(ch)
for r in range(rows):
for c in range(cols):
if board[r][c] in root:
dfs(r, c, root)
return found
Bit toolbox
bin(x), format(x, "08b"), int(s, 2),
x.bit_count() (3.10+) and x.bit_length().
XOR facts: a ^ a == 0, a ^ 0 == a, order
doesn't matter.
def get_bit(x: int, i: int) -> int:
return (x >> i) & 1
def set_bit(x: int, i: int) -> int:
return x | (1 << i)
def clear_bit(x: int, i: int) -> int:
return x & ~(1 << i)
def toggle_bit(x: int, i: int) -> int:
return x ^ (1 << i)
def drop_lowest(x: int) -> int:
return x & (x - 1) # 101100 -> 101000
def lowest_bit(x: int) -> int:
return x & -x # 101100 -> 000100
def is_power_of_two(x: int) -> bool:
return x > 0 and x & (x - 1) == 0
def popcount(x: int) -> int: # x >= 0
count = 0
while x:
x &= x - 1
count += 1
return count
def subsets(items: list) -> list[list]:
n = len(items)
return [[items[i] for i in range(n) if mask >> i & 1]
for mask in range(1 << n)]
Binary trie for maximum XOR
def max_xor(nums: list[int]) -> int:
bits = max(nums).bit_length()
root: dict = {}
best = 0
for x in nums:
node = root # insert x
for i in range(bits - 1, -1, -1):
node = node.setdefault((x >> i) & 1, {})
node, cur = root, 0 # query x
for i in range(bits - 1, -1, -1):
want = 1 - ((x >> i) & 1)
if want in node:
cur |= 1 << i
node = node[want]
else:
node = node[1 - want]
best = max(best, cur)
return best
32-bit problems in Python
Python ints are unbounded and negatives have infinite leading 1s. Mask to emulate fixed width:
MASK = 0xFFFFFFFF
def to_unsigned32(x: int) -> int:
return x & MASK
def to_signed32(x: int) -> int:
x &= MASK
return x - (1 << 32) if x >= 1 << 31 else x
Operation costs
| Operation | Time | Space |
|---|---|---|
| Trie insert / search / starts_with | O(L) | O(L) per insert |
| Trie of N words (total C chars) | O(C) to build | O(C) |
| Wildcard search, d dots | O(26^d · L) worst | O(L) stack |
| Words on an m×n board | O(m·n · 4·3^(L-1)) | O(total chars) |
| & | ^ ~ << >> on machine-size ints | O(1) | — |
| Popcount via x & (x - 1) | O(set bits) | O(1) |
| Enumerate subsets with masks | O(2^n · n) | O(n) |
| Max XOR with a binary trie | O(n · B) | O(n · B) |
Watch for
Forgetting the end-of-word flag: search("ap") must be False when only "app" was inserted.
Mixing up search and starts_with: they share the walk, only search checks the end flag.
Board search: pop the word when found (or you'll report duplicates) and restore the cell after the DFS.
Negative numbers: ~x is -(x + 1), bin(-5) is '-0b101' and x >>= 1 on a negative never reaches 0. Mask with 0xFFFFFFFF for 32-bit problems.
Precedence: + and - bind tighter than shifts, and shifts tighter than & ^ |. 1 << n - 1 means 1 << (n - 1); a ^ b + 1 means a ^ (b + 1). Add parentheses.
Binary trie: insert every number with the same bit width (from the highest bit), or paths won't line up.