Regular Expression

9 Dec 2011

Implement a function that matches a string to a regular expression. The regular expression only contains a-z,'.', and '*'. * matches any string that precedes it, even an empty string . matches a character For example, isMatch("bbb","b.b") --> true isMatch("bbaaab","b*ab") --> false isMatch("bbaaab","b*aaab") --> true isMatch("aaab","b*aaab") --> true

The problem is called for a dynamic programming solution when it seems conditional in each step. (Though it might be an illusion.)

This one actually resembles the famous handwriting recognition algorithm named “Elastic Matching”.

Anyway, we have to preprocess a little and group c* into a single character. This means c* should match a string of c or an empty string

d[i, j] = true iff a[0..i] matches r[0..j] d[i,j] = (1) true iff a[i] == r[j] and d[i-1,j-1] == true (2) true iff r[j] == '.' and d[i-1,j-1] == true (3) true iff r[j] is c* and it can match a[i] and d[i-1,j-1] is true (4) true iff r[j] is c* and it can match a[i] and d[i-1,j] is true (5) true iff r[j] is c* and it can match a[i] and d[i,j-1] is true

if d[n,m] is true, then it's a match.

(3) means that * matches the character as its first. (4) means that * consumes one more character. (5) means that * matches an empty string

It's O(n^2) in time and O(n^2) in space.

As d[i,j] only requires d[i-1,j-1] or d[i-1,j], we can improve the space to O(n).

Give it a kudos