Generate a message out of cutout magazine characters (interview question)

Question

This problem comes out of the dynamic programming chapter in The Algorithm Deisgn Manual by Skiena.

Give an algorithm to determine whether you can generate a given string by pasting cutouts from a magazine. You are given a function that will identify the character and its position on the reverse side of the page for any given character position.

I solved this with with backtracking, but since it's in the dynamic programming chapter I think there must be a recurrence I can't figure out. Can anyone give me a hint?

Answer 1

You can solve it with maximum bipartite matching.

Each character L of the given string forms the left set. (Note, you repeat the characters if the string has repeated characters).

Each pair of characters (R1,R2) of the magazine forms the right set.

L is connected to (r1,r2) iff L=R1 or L=R2.

Find a maximum matching in the resulting graph. If all left vertices are part of the matching, you have the answer. If not, such a string is not possible.

See Maximum Bipartite Matchings for an algorithm.

Not sure if this is optimal though and sorry for not answering exactly as asked.

Answer 2

If you have a recursive backtracking solution, you may be able to apply memoization, which is one way to do dynamic programming.