regular expression (dp solution)

'.' 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

I wrote in recursion way to solve this problem before. This time I use dp. Let str=”0″+str, reg=”0″+reg. Build dp[][] boolean array with str.length+1 and reg.length+1 for row and column separately. dp[i][j]=true means str[1…i] match reg[1…j]. dp rules are as below: If reg.charAt[j] is not ‘.’ or ‘*’, dp[i][j]=dp[i-1][j-1] && reg.charAt(i)==str.chartAt(j) If reg.charAt[j]==‘.’, dp[i][j]=dp[i-1][j-1] If reg.charAt[j]==‘*’, (1)if dp[i-2][j] is true, then dp[i][j]=true. This considers * has 0 times. (2)If dp[i-1][j+1]==true, move from dp[i][j+1]to right until str[j]!=reg[i-1]. This considers * has 1, 2, or more times.

public static boolean isMatch(String s, String p) {
    s = "$" + s;
    p = "$" + p;
    boolean[][] dp = new boolean[p.length()][s.length()];
    dp[0][0] = true;
    for (int i = 1; i < p.length(); i++) {
        if (p.charAt(i) == '.') {
            for (int j = 1; j < s.length(); j++) {
                dp[i][j] = dp[i - 1][j - 1];
            }
        }
        else if (p.charAt(i) != '*') {
            for (int j = 1; j < s.length(); j++) {
                dp[i][j] = dp[i - 1][j - 1] && p.charAt(i) == s.charAt(j);
            }
        }
        else {  // handle with '*'
            for (int j = 0; j < s.length(); j++) {
                boolean fromTop = dp[i - 1][j] || (i > 1 && dp[i - 2][j]);
                boolean fromLeft = j > 0 && dp[i][j - 1] && (p.charAt(i - 1) == '.' || p.charAt(i - 1) == s.charAt(j));
                dp[i][j] = fromTop || fromLeft;
            }
        }
    }
    return dp[p.length() - 1][s.length() - 1];
}

check my code on github: link