# Why not using what you learn in compiler theory? The simple hand written recursive descent regex parser!

• For this problem, we only need to implement two 'productions' to hit the regular expression rules.

These two rules are:

1. symbol => [a-z]| '.'

2. symbol* => epsilon | symbol symbol*

bool isMatch(const char* s, const char* p);

bool match_star(const char* s, const char* p) {
return (isMatch(s, p+2) ||( (s[0] != '\0') && ( (s[0] == p[0]) || (p[0] == '.')) && match_star(s+1, p) ) );
}

bool isMatch(const char* s, const char* p) {
if (s[0] == '\0' && p[0] == '\0') return true;
if (p[1] == '*') {
return match_star(s, p);
}
else {
if (p[0] == '.') {
return isMatch(s+1, p+1);
}
if ('a' <= p[0] && p[0] <= 'z') {
return (s[0] == p[0]) && isMatch(s+1, p+1);
}
return false;
}
}

• It is an excellent idea but some test cases failed util I added some lines.

``````#include <string>

using namespace std;

class Solution {
private:
bool match_star(const char* s, const char* p) {
return (is_match(s, p + 2) || ((s[0] != '\0') && ((s[0] == p[0]) || (p[0] == '.')) && match_star(s + 1, p)));
}
bool is_match(const char* s, const char* p) {
//if (s[0] == '\0') return p[0] == '\0';
if (s[0] == '\0' && p[0] == '\0') return true;
if (p[1] == '*') {
return match_star(s, p);
}
else {
// maybe you forgot to check whether s is empty.
if (s[0] != '\0') {
if (p[0] == '.') {
return is_match(s + 1, p + 1);
}
else {
return (s[0] == p[0]) && is_match(s + 1, p + 1);
}
}
return false;
}
}
public:
bool isMatch(string sStr, string pStr) {
const char* s = sStr.c_str();
const char* p = pStr.c_str();
return is_match(s, p);
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.