Problem context and objectives
Mission briefing
Dungeon strategy engineer · A robot must cross a tiled dungeon
Store enough solved tile states to plan the complete route: The Woven Echo.
A greedy step can trap the robot; recomputing every route is too expensive.
How you win
- 1Recognize when Interleaving string memoization matches the clues
- 2Keep this true after every move: memo[i,j] states whether source suffixes at i and j can form the remaining target suffix
- 3Reach the result within O(mn) time and space
Rules and pressure
- Target cost: O(mn) time and space
- State rule: memo[i,j] states whether source suffixes at i and j can form the remaining target suffix
Lesson 1 of 3
Live algorithm trace
Interleaving string memoization
Complete execution1 of 5
a
target
a
b
b
a
c
The source lengths sum to the target length, so begin at state zero-zero.
1
reject unequal total lengths2
search state (i,j)3
k = i + j in target4
try source one when its character matches5
try source two when its character matches6
memoize success or failurefirst = aabccsecond = dbbcatarget = aadbbcbcac
Truth to preserve / Cost target
Truth to preserve
memo[i,j] states whether source suffixes at i and j can form the remaining target suffix
Cost target
O(mn) time and space
A state needs only positions in the two source strings because their sum determines the target position. Memoization prevents the same ambiguous prefix pair from branching repeatedly.
Your call · What should guide every step of this algorithm?