正则表达式填字游戏 [英] Regex crossword solver

问题描述

在

解决方案

即使您不允许反向引用，也很难解决。从确切的封面保护问题到此问题，都有一个简单的映射。

如果您设置了 S [1]，S [2]，...，S [n] （且并集为 S ），并且不失一般性，集合包含所有N的所有数字1 ... N。表示 S [i] 作为长度为N的字符串，如果k在 S [i] 1 c>，否则 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 * 
  

A解决此正则表达式难题的方法是使用 S [i] 精确覆盖{1、2、3、4}。

Following Find string to regular expression programmatically?, we assume that it takes linear time to find a string that matches a regex. My intiution says that we can solve a regex crossword programmatically too, right?

If yes, what will be the time complexity of solving a NxM regex crossword?

Example:

解决方案

It's NP hard, even if you disallow backreferences. There's a simple mapping from the exact set cover problem to this problem.

If you have sets S[1], S[2], ..., S[n] (with union S), and without loss of generality, the sets contain all the numbers 1...N for some N. Represent the S[i] as a string of length N, with 1 in the k'th place if k is in S[i], and 0 otherwise. Let the columns of your regexp puzzle be all the same -- 0*10*, and the k'th row be "(S[k])|(0*)".

For example, if S[1] = {1, 4}, S[2] = {2}, S[3] = {3}, and S[4] = {2, 3}, then the puzzle would be:

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

A solution to this regexp puzzle is an exact cover of {1, 2, 3, 4} with the S[i].

这篇关于正则表达式填字游戏的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！