检查是否可以通过杂志文章中删除的一组字符创建给定的字符串

Question

"观察当你从杂志中剪切一个角色时,页面背面的角色也会被移除.给出一个算法来确定你是否可以通过粘贴来自给定杂志的剪切来生成给定的字符串.假设你是给定一个函数,该函数将识别字符及其在页面反面的位置,用于任何给定的字符位置."

我该怎么做？

我可以做一些初步的修剪,这样如果一个需要的角色只有一种方法可以被拾取,那么它最初是在转动动态技术的子问题之前采取的,但是在这个初始修剪之后呢？

什么是时间和空间的复杂性？

Answer 1

正如@LiKao建议的那样,这可以使用max flow来解决.为了构建网络,我们制作两个顶点"层":一个包含输入字符串中的所有不同字符,另一个包含页面上的每个位置.如果该位置在一侧具有该字符,则从字符到位置创建容量为1的边缘.使容量1的边缘从每个位置到接收器,并使从源到每个字符的边缘的容量等于输入字符串中该字符的多重性.

例如,假设我们在有四个位置的页面上搜索"FOO"这个词:

pos    1 2 3 4
front  F C O Z
back   O O K Z

然后我们生成以下网络,忽略位置4,因为它不提供任何所需的字符.

现在,我们只需确定是否存在从源到接收器的流量length("FOO") = 3或更多.