从剪下的杂志字符中生成消息（面试问题）

Question

这个问题出自 Skiena 的The Algorithm Deisgn Manual中的动态规划章节。

给出一个算法来确定是否可以通过粘贴杂志的剪纸来生成给定的字符串。您将获得一个函数，该函数将针对任何给定的字符位置识别该字符及其在页面背面的位置。

我用回溯解决了这个问题，但由于它在动态编程章节中，我认为一定有我无法弄清楚的复发。谁能给我一个提示？

Answer 1

您可以通过最大二分匹配来解决它。

给定字符串的每个字符 L 形成左集。（注意，如果字符串有重复字符，则重复这些字符）。

杂志的每对字符（R1，R2）形成正确的集合。

L 连接到 (r1,r2) 当且仅当 L=R1 或 L=R2。

在结果图中找到最大匹配。如果所有左边的顶点都是匹配的一部分，那么您就得到了答案。如果不是，这样的字符串是不可能的。

请参阅算法的最大二分匹配。

不确定这是否是最佳选择，很抱歉没有完全按照要求回答。