Leetcode: Regular Expression Matching

Question

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 <!--more-->

Dynamic Programming

f(i,j) represents whether the first i letters of string s can be matched by the first j letters of regular expression p(0 means no and 1 means yes). Therefore, the recursion formula can be written as:
  (1) if p[i] == '.', f(i,j) = f(i-1,j-1)
  (2) if p[i] == '*', f(i,j) = f(i,j-2) or { s[i] match p[j-1] and f(i-1,j) }
  (3) if p[i] != '.' and p[i] != '*',
    f(i,j) = f(i-1,j-1), when s[i] == p[j]
    f(i,j) = 0, when s[i] != p[j]

bool isMatch(char * s,char * p)
{
    int lens = strlen(s--), lenp = strlen(p--);
    bool f[lens + 1][lenp + 1];
    
    memset(f,0,sizeof(f));
    f[0][0] = 1;
    for(int j = 1;j <= lenp;++j)
        f[0][j] = p[j] == '*' && f[0][j - 2];//init

    for(int j = 1;j <= lenp;++j)
    for(int i = 1;i <= lens;++i)
        if(p[j] == '*')
            f[i][j] = f[i][j - 2] || (s[i] == p[j - 1] || p[j - 1] == '.') && f[i - 1][j];
        else if(s[i] == p[j] || p[j] == '.') 
            f[i][j] = f[i-1][j-1];
    return f[lens][lenp];
}

• Time Complexity: O(n^2)
• Space Complexity: O(n^2)

Finding law

By observing the samples above, we can find the law and solve it directly

bool isMatch(char *s, char *p)
{
    if (*s==0 && *p==0) return true;
    if (*p==0 || (*s==0 && *(p+1)!='*') ) return false;

    if (*(p + 1) != '*')
        return (*p == *s || *p == '.') ? isMatch(s + 1, p + 1) : false;

    do if (isMatch(s, p + 2)) return true;
    while (*s && (*(s++) == *p || *p == '.'));
    return false;
}

• Time Complexity: O(n)
• Space Complexity: O(1)