检查给定的字符串是否可以由从杂志文章中剪下的字符集创建

Question

"观察一下，当你从杂志上剪下一个字符时，背面的字符也会被剪掉。提供一个算法来确定是否可以通过从给定的杂志上剪下字符来生成给定的字符串。假设您有一个函数，该函数将识别任何给定字符位置的字符及其在背面页面上的位置。"

我该怎么做呢？

我可以进行一些初始修剪，以便如果需要的字符只有一种选择方式，则在使用动态技术的子问题之前最先被选中，但是在这个初始修剪之后该怎么办呢？

时间和空间复杂度是多少？

- xyz

---

我的猜测是，你可以以某种方式将其简化为最小割/最大流问题，但我还不确定如何做到这一点。大致上可以将字符组合作为图中的链接，字符串作为流量。我晚些时候会更仔细地考虑这个问题。 - LiKao

Answer 1

正如@LiKao所建议的那样，可以使用最大流算法来解决这个问题。为了构建网络，我们将字符串中所有不同的字符作为一层顶点，页面上每个位置都作为另一层顶点。如果某个位置有一个特定字符，则从该字符到该位置之间连一条容量为1的边。从每个位置向汇点连一条容量为1的边，从源点向每个字符连一条容量等于该字符在输入字符串中出现的次数的边。

例如，假设我们要在一个长度为四的页面上搜索单词"FOO"：

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

我们生成了以下网络，忽略位置4，因为它没有提供所需的任何字符。

现在，我们只需要确定是否存在从源到汇流的长度为length("FOO") = 3或更长的流量。

- hammar

---

这个解决方案是否与通过最大流算法解决任务分配有关？ - mcdowella

@mcdowella：是的。这解决了将页面上的位置分配给输入字符串中的字符的问题。 - hammar

@Jack：不，重点在于每个部件只能使用一次，但您可以选择它们的顺序以及从每个部件中使用哪一面。 - hammar

我也认为最大流是解决这个练习的正确方法，然而，在Skiena的书中，这个练习被列在动态规划部分。难道有一种使用动态规划的时间和空间效率高的解决方案吗？ - axel22

@axel22 你能为这个问题想出一个DP解决方案吗？我已经制定了一个，但是没有看到与暴力搜索相比的任何好处。让 S 成为从切口中取出的字母序列，X 是要生成的字符串。以位置 j 结尾的字符串可以使用 1..i 个字母（S[0..i]）生成。如果 i > 0，j > 0，则 dp[i][j] = (dp[i-1][j-1] && (S[i]_f == X[j] || S[i]_r == X[j])) || dp[i-1][j]，未显示基本条件。 - Abhijit Sarkar

Answer 2

您可以直接使用动态规划。

给定一个长度为n的字符串s和一组片段P = {p_1, ..., p_k}，其中每个片段在前面有一个字母p_i.f，在后面有另一个字母p_i.b。

记f(j, p)函数返回true，表示可以使用p中的片段创建子串s_1...s_j，否则返回false。

以下递归式成立： f(n, P) = f(n-1, P-p_1) | f(n-1, P-p_2) | ... | f(n-1, P-p_k)

简单来说，使用所有片段P创建子串s的可行性取决于使用除去一个片段后的子串s_1...s_n-1的可行性，我们尝试删除所有可能的片段（在实践中，我们不需要逐个删除所有片段；我们只需要删除那些 p_i.f == s_n || p_i.b == s_n 的片段即可）。

初始条件是f(1, P-p_1) = f(1, P-p2) = ... = true，假设我们已经预先检查了P中是否有足够的字母以覆盖s中的所有字母（这可以在线性时间内完成）。

- kounoupis

---

P的子集呈指数级增长，因此对于某些输入，动态规划可能不适用。 - axel22

是的，你说得对。在最坏情况下，这将会检查所有可能的子集。此外，递归关系也没有正确地被表述。 - kounoupis

Answer 3

虽然这个问题可以像已接受的答案所示一样被制定为最大流问题，但在二分图中将其制定为最大基数匹配问题会更简单、更高效。Maxflow算法（比如Dinic's）比特殊情况算法（比如Hopcroft-Karp算法）慢。

二分图是通过从给定字符串的每个字符添加两条边到一个切口来形成的，每个边都对应于一个侧面。然后我们运行Hopcroft–Karp。最后，我们只需检查匹配的基数是否等于字符串的长度即可。

有一个使用 JGraphT 实现（用Scala编写）的可工作实现，请参阅我的 GitHub。

我想提出一个更高效的 DP 解法，因为 Skiena 的书在 DP 部分有这个问题，但目前还没有找到任何解决方案。

- Abhijit Sarkar