10981 - String Morphing
Determine the steps to morph a string to a character by a set of "grammar", subject to certain requirements.
There is an obvious algorithm to check if a string can be morphed to our desired character (such an algorithm is known as CYK algorithm). Based on this we can get a simple algorithm to meet the requirements.
1. A top-down DP works much faster than a bottom-up DP in this problem.
2. Somebody claims that backtracking also works for this task.
3 bbbba a bbbba b bbbba c
bbbba bbba bba bc a None exist! bbbba bbba bba ba c