My recursive cpp code using derivatives

• ``````class Solution {
public:
// isMatch(a..., c<Re>) = false
// isMatch(c..., c<Re>) = isMatch(..., <Re>)
// isMatch(c..., .<Re>) = isMatch(..., <Re>)

// isMatch(a..., c*<Re>) = isMatch(a..., <Re>)
// isMatch(c..., c*<Re>) = isMatch(..., c*<Re>) || isMatch(c..., <Re>)
// isMatch(c..., .*<Re>) = isMatch(..., .*<Re>) || isMatch(c..., <Re>)

// isMatch(c..., "") = false
// isMatch("", <Re>) = containNull(<Re>)

// containNull(c<Re>) = false
// containNull(c*<Re>) = containNull(<Re>)
// containNull("") = true

bool containNull(const string& p, int start, int end)
{
if(start == end) return true;
if(end == start+1) return false;
if(p[start+1] == '*') return containNull(p, start+2, end);
return false;
}

bool isMatchHelper(const string& s, int s_start, int s_end,
const string& p, int p_start, int p_end)
{
if(s_start == s_end) return containNull(p, p_start, p_end);
if(p_start == p_end) return false;

if(p_start <= p_end-2 && p[p_start+1] == '*')
{
if(s[s_start] == p[p_start] || p[p_start] == '.')
return isMatchHelper(s, s_start+1, s_end, p, p_start, p_end)
|| isMatchHelper(s, s_start, s_end, p, p_start+2, p_end);
else
return isMatchHelper(s, s_start, s_end, p, p_start+2, p_end);
}

if(s[s_start] == p[p_start] || p[p_start] == '.')
return isMatchHelper(s, s_start+1, s_end, p, p_start+1, p_end);
else
return false;
}

bool isMatch(string s, string p)
{
return isMatchHelper(s, 0, s.size(), p, 0, p.size());
}
};``````

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