Create a message from cutout log characters (interview question)

Question

This problem arises from the dynamic programming chapter in the Skiena Deisgn Algorithm Guide.

Give an algorithm to determine if you can create a given row by inserting cutouts from the log. You are given a function that identifies the character and its position on the back of the page for any given character position.

I solved this with backtracking, but since it’s at the head of dynamic programming, I think there should be a repetition that I cannot understand. Can someone give me a hint?

Answer 1

You can solve it with maximum two way match.

Each L character of a given string forms a left set. (Note that you are repeating characters if the string contains duplicate characters).

Each pair of characters (R1, R2) of the log forms the correct set.

L connects to (r1, r2) if L = R1 or L = R2.

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

See Maximum Two-way Matches for an algorithm.

Not sure if this is optimal, although sorry for not responding exactly as asked.

Answer 2

If you have a recursive backtracking solution, you can apply memoization , which is one way of dynamic programming.