Match a regular expression (including '.' and '*' using dynamic programming

regexp_match.cpp

bool canMatch(char a, char b)
{
    return (a == b || b == '.');
}

bool isMatch(const char *s, const char *p) {
    int lS = strlen(s);
    int lP = strlen(p);
    vector<vector<bool> > F(lS + 1, vector<bool>(lP + 1));
    F[0][0] = true;
    for (int i = 0; i <= lS; i++)
	{
        for (int j = 1; j <= lP; j++)
        {
            if(i>0)
                // matches one character, index of both string and pattern move forward by 1
                if (F[i-1][j-1] && canMatch(s[i-1], p[j-1]))
                {
                    F[i][j] = true;
                    continue;
                }
            if (i > 0 && j > 1)
                // matches the situation when the next char in the string is the same as the char before the '*' in the pattern
                // pre-match: string xxxCyyy, pattern mmmC*nnn, xxx matches mmmC*
                // current match: xxxC matches mmmC*
                if (F[i-1][j] && canMatch(s[i-1], p[j-2]) && p[j-1] == '*')
                {
                    F[i][j] = true;
                    continue;
                }
            if (j > 1)
                // matches the situation when the next two chars in the pattern is in the form of C*
                // pre-match: string xxxyyy, pattern mmmC*nnn, xxx matches mmm
                // current match: xxx matches mmmC*
                if (F[i][j-2] && p[j-1] == '*')
                {
                    F[i][j] = true;
                    continue;
                }
        }
    }
    return F[lS][lP];
}

Hey, can you please explain the code in detail. I am not able to understand why are you taking an array of size ls+1 and lp+1???

This is for the base case