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
C++:
01 bool isMatchHelp(const char *s, const char *p, int m, int n)
02 {
03      if((s[m]=='')&&(p[n]==''))  return true;
04      if(p[n]=='') return false;
05      if(p[n+1]=='*')
06      {
07          int t=m;
08          do
09          {
10              if(isMatchHelp(s,p,t,n+2))  return true;
11          }while(((s[t]==p[n])||(p[n]=='.'))&&(s[t++]!=''));
12      }
13      else
14      {
15          if(p[n]=='.')
16          {
17            return (s[m]!='')&&(isMatchHelp(s,p,m+1,n+1));
18          }
19          return (s[m]==p[n])&&(isMatchHelp(s,p,m+1,n+1));
20      }
21      return false;
22  }
23  class Solution {
24  public:
25      bool isMatch(const char *s, const char *p) {
26          // Start typing your C/C++ solution below
27          // DO NOT write int main() function    
28          return isMatchHelp(s,p,0,0);
29      }
30  };
Advertisements
This entry was posted in Recursive, String. Bookmark the permalink.

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s