6.4

Reconstructing a String of Words

Pattern · prefix over one string 1-D Boolean table O(n²) 5difficulty
Question — exam style

You are given a string of n characters s[1…n], which you believe to be a corrupted text document in which all punctuation has vanished (so that it looks like "itwasthebestoftimes…"). You wish to reconstruct the document using a dictionary, available as a Boolean function dict(w) that returns true iff string w is a valid word.

Input:String s[1..n]; oracle dict(·) answering in O(1).
Output:(a) Whether s can be split into valid words (O(n²)); (b) if so, the corresponding sequence of words.

Model answer

4-part format
aSubproblem in words
T(i) = true iff the prefix s[1..i] can be split into a sequence of valid dictionary words, for 0 ≤ i ≤ n.

Boolean table — a legal primitive. T(0) = true represents the empty prefix (splittable trivially), which anchors the recurrence.

bRecurrence math only, with base case + bounds
T(0) = true T(i) = OR over 1 ≤ j ≤ i of ( T(j-1) AND dict( s[j..i] ) ) for 1 ≤ i ≤ n

The prefix s[1..i] splits iff its last word is some s[j..i] that is valid and the part before it, s[1..j−1], also splits.

cImplementation analysis
(1) # of subproblems
O(n)
(2) Time to fill table
O(n²) — O(n) choices of j
(3) Where answer is extracted
trace prev(·) from n
(4) Time to extract
O(n)
Read the Output line: it wants the words, not just yes/no

DPV 6.4(b) asks you to output the sequence of words, so extraction is not an O(1) lookup of T(n). Store a companion array prev(i) = the j that made T(i) true (a primitive index — still legal), then trace back from n, emitting s[j..i] at each step. That's O(n) extraction. If the exam only asks the decision ("can it be split?"), then it's T(n) in O(1) — match your analysis to what's actually asked.

Optional pseudocode not required by Ed #9

A mechanical translation of the recurrence, with the back-pointer for word reconstruction.

function WordBreak(s[1..n], dict):
    T[0] = true
    for i = 1 to n:
        T[i] = false
        for j = 1 to i:
            if T[j-1] and dict(s[j..i]):
                T[i] = true; prev[i] = j; break
    if not T[n]: return false
    # reconstruct words by tracing prev from n back to 0
    words = []; i = n
    while i > 0: j = prev[i]; prepend s[j..i] to words; i = j-1
    return words
✎

Try it yourself

worked example + self-test

Recurrence: T(0)=true; T(i)=ORj(T(j−1) AND dict(s[j..i])). Words via back-pointers.

Worked boolean table shown

s = "applepenapple" dict = { apple, pen }

i │ 0 │ 1 2 3 4 │ 5 │ 6 7 │ 8 │ 9 10 11 12 │ 13 char │ – │ a p p l │ e │ p e │ n │ a p p l │ e T(i) │ T │ F F F F │ T │ F F │ T │ F F F F │ T T(5)=T via j=1: s[1..5]="apple", T(0)=T T(8)=T via j=6: s[6..8]="pen", T(5)=T T(13)=T via j=9: s[9..13]="apple", T(8)=T
Answer: T(13) = true. Words (trace 13→8→5→0): apple · pen · apple.
Self-test greedy-longest fails here — work the table

s = "cars" dict = { car, ca, rs }

Reveal answer
Splittable = true, words ca · rs. Note the trap: greedy takes "car" first, then chokes on the leftover "s" — the DP backtracks to the shorter first word. (T(0..4) = T F T T T.)
More practice 5 problems · reveal each

Build the Boolean table T[0..n] for each, then reveal. Mix of clean splits, a greedy trap, a non-splittable case, and overlapping words.

1.  s = "leetcode" dict = { leet, code }

Reveal
true → leet · code.  (warm-up; T flips true only at 4 and 8)

2.  s = "catsanddog" dict = { cat, cats, and, sand, dog }

Reveal
true → cat · sand · dog  (also valid: cats · and · dog — two paths reach T(10)).

3.  s = "carsn" dict = { cars, car, sn, s, n } — greedy trap

Reveal
true → car · sn.  Greedy-longest grabs "cars" first, then dead-ends on "n" (not a word). The DP takes the shorter "car" and finds "sn". (T = T F F T T T.)

4.  s = "catsandog" dict = { cats, cat, sand, and, dog } — the negative case

Reveal
false — not splittable. You can reach "catsand" (cat·sand, T(7)=true) but "og" is not a word and nothing else closes the gap. The DP correctly returns false at T(9). (T = T F F T T F F T F F.)

5.  s = "ilikecoding" dict = { i, like, coding, cod, ing, ilike }

Reveal
true → ilike · coding  (also i · like · cod · ing and i · like · coding — several overlapping paths all reach T(11)).