正则表达式填字游戏求解器

Question

正在关注 Find string to regular expression programmatically? ，我们假设找到与正则表达式匹配的字符串需要线性时间。我的直觉告诉我们，我们也可以通过编程方式解决正则表达式填字游戏，对吧？

如果是，解决 NxM 正则表达式填字游戏的时间复杂度是多少？

例子:

Answer 1

即使您不允许反向引用，它也是 NP 难题。 exact set cover problem 有一个简单的映射对这个问题。

如果您有集合 S[1]、S[2]、...、S[n](带有 union S)，并且不失一般性，这些集合包含所有数字 1...N 对于某些 N。将 S[i] 表示为长度为 N 的字符串，1 在第 k 个如果 k 在 S[i] 中，则放在 0 中。让您的正则表达式拼图的列都相同 -- 0*10*，第 k 行是“(S[k])|(0*)”。

例如，如果 S[1] = {1, 4}，S[2] = {2}，S[3] = {3}，并且 S[4 ] = {2, 3}，那么谜题就是:

         0*10*  0*10*  0*10*  0*10*
1001|0*
0100|0*
0010|0*
0110|0*

这个正则表达式难题的解决方案是用 S[i] 精确覆盖 {1, 2, 3, 4}。