leetcode: Regular Expression Matching

Regular Expression Matching Problem Description:

Implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") ? false
isMatch("aa","aa") ? true
isMatch("aaa","aa") ? false
isMatch("aa", "a*") ? true
isMatch("aa", ".*") ? true
isMatch("ab", ".*") ? true
isMatch("aab", "c*a*b") ? true

Regular Expression Matching Solution and Precautions:

Basically, the recursive solution could pass OJ as show in “Regular Expression Matching“. But several points worth noting:

To my knowledge:

(1) Be careful about the definition of matching, it is totally different from wildcard matching, and the greedy algorithm for wildcard matching will fail here for regular expression matching, consider this case: abbaa, ab*a*c*a, then the greedy algorithm will keep the last ‘*’ and keep it as c*, so when matching bb, it will always fail. But the correct solution is that it is true, these two string matches.

(2) DP might also work here. But it becomes more complicated than wildcard matching, since a* is a complete pattern rather than a single ‘*’ is a complete pattern. You can code DP anyways but I think it is not worthwhile in an interview.

Written on June 23, 2013