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 isMatch(const char *s, const char *p)
02  {
03       if((s[0]==)&&(p[0]==))
04              return true;
05       if(p[0]==)
06                return false;
07       if(p[1]!=‘*’){
08          if((p[0]==s[0])||((p[0]==‘.’)&&(s[0]!=)))
09              return isMatch(s+1,p+1);
10          else
11              return false;
12      }
13      else if(p[1]==‘*’){
14          while((p[0]==s[0])||((p[0]==‘.’)&&(s[0]!=))){
15              if (isMatch(s,p+2))
16                  return true;
17              else
18                  s++;
19          }
20          return (isMatch(s,p+2));
21      }
22 }
Advertisements
This entry was posted in Backtrack, 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