Construction and Exploration
What is this?
Choose, recurse, undo. Every problem here uses that same skeleton, and every one is decided by something else: what you know before the recursion starts. A validity rule that kills a segment immediately. A prefix map that offers only words which can legally follow. A union-find that groups synonyms up front, so the search that remains is a plain product over the groups. And one problem where you cannot see the input at all.
Fun fact: Word Squares has a constraint that is easy to miss on the first read. The square must read the same across and down, so once
krows are placed, rowkis already fixed in its firstkcharacters: they are thek-th letters of the rows above. The candidate list is not "all words", it is "all words with this exact prefix". A prefix to words map makes that lookup cheap, and the map is four lines. The search is still exponential in the worst case, but most prefixes match few or no words, so most branches die at once.
🔓 The 4 problems in this chapter are free. Sign in with Google or Microsoft to start solving.
Core idea: write the recursion in thirty seconds, then spend the rest of your time on the cheapest test that proves a branch is dead. That test is most of the solution.
1. Reject per segment, not per candidate
def bt(i, parts):
if len(parts) == 4:
if i == len(s): out.append(".".join(parts))
return
for L in (1, 2, 3):
if i + L > len(s): break
seg = s[i:i+L]
if (seg[0] == '0' and L > 1) or int(seg) > 255: continue # dead now
bt(i + L, parts + [seg])
Both rejections happen the instant a segment is formed, so no branch survives to depth four just to be discarded. The leading-zero rule is the one people forget: "0" is valid, "01" is not, and it costs a single clause.
The tree has at most three branches per level over four levels, so the backtracking visits at most 3^4 = 81 full paths whatever the input length, and its time and space are O(1). That sounds wrong, so say why. The brute-force alternative, trying every choice of three dot positions among n - 1 gaps, is O(n^4) for a general n; it only looks small because the inputs here are short.
2. Precompute the legal candidates
pref = defaultdict(list)
for w in words:
for i in range(n + 1):
pref[w[:i]].append(w) # every prefix maps to the words holding it
def bt(square):
if len(square) == n: out.append(square[:]); return
k = len(square)
p = "".join(w[k] for w in square) # column k of the rows already placed
for cand in pref[p]: # only words that can legally follow
square.append(cand); bt(square); square.pop()
The line that carries everything is p: reading down column k of the placed rows gives the prefix row k must start with. Without the map you would filter the whole word list at every node; with it, you index straight to the survivors.
A trie is the textbook alternative and is asymptotically the same. The hash map is shorter to write and easier to explain under time pressure. Mention both, pick one, move on.
3. Group first, and the search dissolves
The problem defines synonyms as transitive: if a ~ b and b ~ c then all three are interchangeable, so union-find gives the equivalence classes. That is a simplification, not a fact about language. Real synonym resources are not transitive, because a word has several senses, so production code would not take the closure this way. Once the classes exist, each word in the sentence contributes either one option or its whole sorted group, and the answer is their product in order. Sorting each group is what makes the search emit in lexicographic order. I would still sort the final list, because it is cheap next to producing the output and removes any doubt.
4. Explore what you cannot see
def bt(r, c, d):
clean(); seen.add((r, c))
for k in range(4):
nd = (d + k) % 4
nr, nc = r + dr[nd], c + dc[nd]
if (nr, nc) not in seen and move():
bt(nr, nc, nd)
go_back() # turnRight ×2, move, turnRight ×2
turnRight()
Coordinates are tracked relative to the start because there is no origin to ask about. seen is checked before move(), so the robot never steps into a visited cell just to step back out. move() returning false means a wall, which is how the room is discovered. And the undo is physical: turn around, move one, turn around again. That restores both position and heading, since a robot that returns facing the wrong way corrupts every subsequent direction.
5. A 30-second worked example (IP addresses)
s = "101023"
"1" · "0" · "10" · "23" ✓ 1.0.10.23
"1" · "0" · "102" · "3" ✓ 1.0.102.3
"10" · "1" · "0" · "23" ✓ 10.1.0.23
"10" · "10" · "2" · "3" ✓ 10.10.2.3
"101" · "0" · "2" · "3" ✓ 101.0.2.3
pruned immediately:
"1" · "01" · … ✗ leading zero
"10" · "10" · "23" · "" ✗ fourth segment empty
Five valid addresses. Note "1" · "01" dies at depth two and is never extended, which is the whole point. A version that assembles all four segments first and validates at the end visits more nodes for the same answer (45 against 26 for this string).
6. Where you'll actually meet this
- Network tooling. Parsing and validating address strings under strict format rules.
- Robotics. A robot with no map and only relative moves has to track its own position as it explores. The problem is a toy version; real robots add sensors and drift correction.
- Crossword and puzzle construction. Word squares are constraint satisfaction at small scale.
- Search query expansion. Expanding a phrase across groups of alternative words has the same product shape, though real synonym sets are not transitive.
7. Problems in this chapter
Restore IP Addresses
Every valid IP address formable from a digit string. Reject a segment the moment it exceeds 255 or carries a leading zero.
Pattern: backtracking with per-segment validation. Target: O(1) time and space, since the tree has at most 81 paths. Brute force over dot positions is O(n^4).
Word Squares
All squares reading identically across and down. Build a prefix to words map, then place rows against the prefix the placed columns dictate.
Pattern: backtracking + precomputed candidates. Target: index build O(N · L^2) for N words of length L; the search is exponential in the worst case and pruned hard by prefixes in practice.
Robot Room Cleaner
Clean an unknown room through a move API. Track relative coordinates, check visited before moving, and undo each move with a physical go-back routine.
Pattern: blind DFS with state restoration. Target: O(N) robot commands and O(N) space for N reachable open cells.
Synonymous Sentences
All sentences formed by substituting synonyms, in lexicographic order. Union-find the synonym pairs, sort each group, then take the ordered product.
Pattern: union-find + enumeration. Target: clustering in about O(V + E), then O(P · L) to emit P sentences of L words, which is output-bound.
8. Common pitfalls
- Validating only at the leaf. Rejecting a segment on creation is the entire optimisation.
- Allowing leading zeros.
"0"is a valid segment,"01"is not. - Filtering the whole word list at each node instead of indexing a prefix map.
- Forgetting that word squares must read both ways, which is what determines the required prefix.
- Restoring position but not heading in the robot's go-back routine.
- Treating synonyms as pairs rather than as classes. The problem defines the relation as transitive, so chains must merge.
- Relying only on the final sort in the sentence problem. Sorting each small group beforehand makes the search emit in order; a final sort is just a cheap safety net.
- Calling
move()before checkingseenin the robot problem, which sends the robot into a visited cell that you then have to back out of. - Claiming a bound for Word Squares that does not hold. The worst case is exponential; say so and explain the prefix pruning.
9. Key takeaways
- The recursion is boilerplate. The pruning is the algorithm.
- Reject at the earliest provable death, not at the leaf.
- A prefix map converts "try everything" into "try what can work". It is four lines, though the worst case stays exponential.
- Undo is not always an assignment. Sometimes it is four API calls, and both position and heading must return.
- Preprocessing can remove the search. Union-find turns one of these into a product.
- A bounded tree means
O(1). Restore IP Addresses has at most 81 paths, but the brute force over dot positions isO(n^4). - Why interviewers like it: everyone writes the same recursion, so the pruning is the only thing that distinguishes answers.
Order: Restore IP Addresses → Word Squares → Robot Room Cleaner → Synonymous Sentences.
Restore IP Addresses
Core idea: An IPv4 address is four numbers, each
0..255, joined by three dots. Restoring a digit string means choosing where the three dots go, which is the same as cutting the string into four pieces. Each piece is 1, 2 or 3 digits long, so at every cut you try those three lengths, check the piece you just carved (in range, no leading zero) and recurse on the rest. A check on the leftover length ("can the digits I have left still fill the segments I have left?") cuts the tree down further.
Problem, rephrased
You are cleaning a scraped log in which an upstream tool stripped the dots out of every IP address. What should read 255.255.11.135 arrives as the bare digit run "25525511135". You get a string s of digits.
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson