17.2 (Java) Problem clarification

**daemoohn** · June 22, 2016, 12:43am

I didn’t understand the problem requirement at all.
We already have a string and a given regular expression, we have to generate the closest match from that regular expression to the given string?
Like string=abba and pattern a(b{0,})a. In this case the closest match is abba with distance 0.
The way I’m feeling, this heads to A* search?

**tsunghsienlee** · October 3, 2016, 4:33am

The problem here is that regular expression has many different almost infinite combinations on that. So you need to find an algorithm to find the shortest edit distance to that.