Regular Expression Matching

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

/*
dp[i][j] == true: the substring from 0 to index i of string s can match with the substring from 0 to index j of string p

When we compute each dp[i][j], there are four conditions:
1. p.charAt(j-1) == s.charAt(i-1)    
    --> dp[i][j] = dp[i - 1][j - 1];
2. p.charAt(j-1) == '.'                     
    --> dp[i][j] = dp[i - 1][j - 1];
3. p.charAt(j-1) == '*' 
   • p.charAt(j-2) == s.charAt(i-1) or p.charAt(j-2) == '.'
    --> dp[i][j] = dp[i][j - 1] ||   //a* counts as single a
                   dp[i][j - 2] ||   //a* counts as empty
                   dp[i - 1][j]      //a* counts as multiple a
   • else 
    --> dp[i][j] = dp[i][j - 2]      //a* counts as empty
4. else
    --> dp[i][j] = false

Notice the initialization in this problem.

Notice the special case:
1. s = "", p = "*a", return false;
2. s = "", p = "**", return true;

time:O(m*n), space:O(m*n)
*/


public class Solution {
    public boolean isMatch(String s, String p) {
        if (s == null && p == null) {
            return true;
        }
        if (s == null || p == null) {
            return false;
        }
        int sl = s.length();
        int pl = p.length();
        //match[x][y]: s.substring(0,x) matches p.substring(0,y)
        boolean[][] match = new boolean[sl + 1][pl + 1]; 
        match[0][0] = true;
        for (int j = 2; j <= pl; j++) {
            if (p.charAt(j - 1) == '*') {
                match[0][j] = match[0][j - 2];  //match[0][1] must be false;
            }
        }
        for (int i = 1; i <= sl; i++) {
            for (int j = 1; j <= pl; j++) {
                if (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.') {
                    match[i][j] = match[i - 1][j - 1];
                } 
                else if (p.charAt(j - 1) == '*') {
                    if (j - 2 < 0) {
                        continue;
                    }
                    if (s.charAt(i - 1) != p.charAt(j - 2) && 
                        p.charAt(j - 2) != '.') {
                        match[i][j] = match[i][j - 2];
                    } else {
                        match[i][j] = match[i][j - 2] || match[i][j - 1] || 
                                      match[i - 1][j];
                    }
                }
            }
        }
        return match[sl][pl];
    }
}