Regular Expression II

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:

int isMatch(const char *s, const char *p)

Some examples:

isMatch("aa","a") → 0
isMatch("aa","aa") → 1
isMatch("aaa","aa") → 0
isMatch("aa", "a*") → 1
isMatch("aa", ".*") → 1
isMatch("ab", ".*") → 1
isMatch("aab", "c*a*b") → 1

Return 0 / 1 ( 0 for false, 1 for true ) for this problem

Solution:

Time: O(mn)
Space: O(mn)

public class Solution {
    // DO NOT MODIFY THE ARGUMENTS WITH "final" PREFIX. IT IS READ ONLY
    public int isMatch(final String A, final String B) {
        // state
        // dp[i][j] = B[0 - i) can match A[o - j)
        // transition
        // dp[i][j] = if B[i] == A[j] || B[i] == '.'
        //               dp[i - 1][j - 1]
        //            if B[i] == '*'
        //               dp[i - 2][j]   || dp[i][j - 1] && B[i - 1] == A[j] || '.'
        //              ignore B[i - 1]        use B[i - 1] 
        // init
        // dp[0][0] = true
        // dp[i][0] = true if B[i] = '*' && dp[i - 2]
        // answer
        // dp[m][n]
        int m = B.length();
        int n = A.length();
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
        for (int i = 2; i <= m; i ++) {
            char r = B.charAt(i - 1);
            if (r == '*' && dp[i - 2][0]) {
                dp[i][0] = true;
            }
        }
        for (int i = 1; i <= m; i ++) {
            for (int j = 1; j <= n; j ++) {
                char c = A.charAt(j - 1);
                char r = B.charAt(i - 1);
                if (c == r || r == '.') {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (r == '*') {
                    dp[i][j] = dp[i - 2][j] || dp[i][j - 1] && i >= 2 && (c == B.charAt(i - 2) || '.' == B.charAt(i - 2));
                }
            }
        }
        // for (int i = 0; i <= m; i ++) {
        //     System.out.println(Arrays.toString(dp[i]));
        // }
        return dp[m][n] ? 1 : 0;
    }
}