[Leetcode] Regular Expression Matching

Regular Expression Matching
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

My Idea
At the beginning, I had a wrong understanding about ‘*’. I was thinking it could be used as 0 or multiple characters. Actually ‘*’ Matches zero or more of the preceding element.

The regex pattern “.*” matches the string “ab”. “.*” means repeat the preceding element 0 or more times. Here, the “preceding” element is the dot character in the pattern, which can match any characters. Therefore, the regex pattern “.*” allows the dot to be repeated any number of times, which matches any string (even an empty string).

Please note that ‘*’ in regular expression is different from wildcard matching, as we match the previous character 0 or more times.

We need some kind of backtracking mechanism such that when a matching fails, we return to the last successful matching state and attempt to match more characters in s with ‘*’. This approach leads naturally to recursion.

Reference:
http://leetcode.com/2011/09/regular-expression-matching.html
Solution

class Solution {
public:
   bool isMatch(const char *s, const char *p) {
      assert(s && p);
      if (*p == '') return *s == '';
     
      // next char is not '*': must match current character
      if (*(p+1) != '*') {
        assert(*p != '*');
        return ((*p == *s) || (*p == '.' && *s != '')) && isMatch(s+1, p+1);
      }
      // next char is '*'
      while ((*p == *s) || (*p == '.' && *s != '')) {
        if (isMatch(s, p+2)) return true;
        s++;
      }
      return isMatch(s, p+2);
    }
};
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s