# UVa 10981

## Summary

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

## Explanation

There is an obvious ${\displaystyle O(n^{3})}$ 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 ${\displaystyle O(n^{4})}$ algorithm to meet the requirements.

## Notes

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
```