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)`

.