UVa 10981

From Algorithmist
Jump to navigation Jump to search

10981 - String Morphing[edit]

Summary[edit]

Determine the steps to morph a string to a character by a set of "grammar", subject to certain requirements.

Explanation[edit]

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.

Notes[edit]

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.

Input[edit]

3
bbbba
a
bbbba
b
bbbba
c

Output[edit]

bbbba
bbba
bba
bc
a

None exist!

bbbba
bbba
bba
ba
c