Yee’s Blog

Practicing Thinking Learning Sharing .

LeetCode: Regular Expression Matching

Implement regular expression matching with support for ‘.’ and ‘*’. sequence is:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

'.' 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

Solution

recurcive implementation:

(Regular_Expression_Matching.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
       assert(p && s);
       if ( *p ＝= '\0') return *s == '\0';
       if (*(p+1) != '*') {
           assert(*p != '*');
           return ((*p == *s) || (*p == '.' && *s != '\0')) && isMatch(s+1, p+1);
       }
       while ((*p == *s) || (*p == '.' && *s != '\0')) {
            if (isMatch(s, p+2)) return true;
            s++;
     }
     return isMatch(s, p+2);
};