2

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:

enter image description here

gsamaras
  • 71,951
  • 46
  • 188
  • 305

1 Answers1

1

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].

Paul Hankin
  • 54,811
  • 11
  • 92
  • 118
  • "even if you disallow backreferences." What do you mean? – gsamaras Sep 20 '17 at 07:24
  • Your example in the question has `\1` and `\2` which are not part of regular expressions, although some implementations allow them. In general, determining if a regexp with backreferences matches a string requires exponential time. – Paul Hankin Sep 20 '17 at 07:25