A table of yes and no

Not every table holds a number. Reachability over prefixes is often all you need.

Key idea

The state sentence, again

The answer at position i is whether the first i characters can be fully consumed by valid pieces. Base case: the empty prefix is reachable.

The transition asks, for each position j before i, whether j was reachable and whether the piece from j to i is valid. If any such j exists, i is reachable.

This is the counting lesson with any in place of a sum. The structure is identical and the reading of the table is different.

1text = "applepen"2pieces = {"apple", "pen"}3 4# Positions reachable by exact pieces, worked out up to 5 characters in.5reachable = [True, False, False, False, False, True, False, False, False]6 7i = 88witnesses = [j for j in range(i) if reachable[j] and text[j:i] in pieces]9print("cuts that reach position 8:", witnesses)10print("the piece each one uses:", [text[j:i] for j in witnesses])

Position 8 is reachable because position 5 was, and 'pen' bridges the gap.

Predict the output· 5 min

Predict the output: one witness is enough

Positions reachable by exact pieces are computed, and for each one every cut point that reaches it is listed. Type the four lines it prints.

Python

1text = "aaa"2pieces = {"a", "aa"}3 4reachable = [True] + [False] * len(text)5for i in range(1, len(text) + 1):6    witnesses = [j for j in range(i) if reachable[j] and text[j:i] in pieces]7    reachable[i] = bool(witnesses)8    print("position", i, "reachable via cuts at", witnesses)9 10print(reachable)

Printed output

Problem· 28 min

Word Break

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

1text = "applepen"2pieces = {"apple", "pen"}3 4# Positions reachable by exact pieces, worked out up to 5 characters in.5reachable = [True, False, False, False, False, True, False, False, False]6 7i = 88witnesses = [j for j in range(i) if reachable[j] and text[j:i] in pieces]9print("cuts that reach position 8:", witnesses)10print("the piece each one uses:", [text[j:i] for j in witnesses])

1text = "aaa"2pieces = {"a", "aa"}3 4reachable = [True] + [False] * len(text)5for i in range(1, len(text) + 1):6 witnesses = [j for j in range(i) if reachable[j] and text[j:i] in pieces]7 reachable[i] = bool(witnesses)8 print("position", i, "reachable via cuts at", witnesses)9 10print(reachable)