10. 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求解。dp[i][j]， i表示str中的index, j表示pattern中的index
如果当前str和pattern字符可以匹配或者p[j] == '.', dp[i][j] = dp[i-1][j-1]
如果p[j] == '*',

1. if str[i] != p[j-1] 且p[j-1] != '.', dp[i][j]， dp[i][j] = dp[i][j-2](0 occurrence of p[j-1])
2. else dp[i][j] = dp[i-1][j] || dp[i][j-1] || dp[i][j-2]
   其余情况为false

public class Solution {
    public boolean isMatch(String s, String p) {
        if(s == null || p == null) return false;
        boolean [][] dp = new boolean[s.length()+1][p.length()+1];
        
        dp[0][0] = true;
        for(int i=0; i<p.length(); i++){
            if(p.charAt(i) == '*' && i>0 && dp[0][i-1]) dp[0][i+1] = true;
        }
        
        for(int i=0; i<s.length(); i++){
            for(int j=0; j<p.length(); j++){
                if(p.charAt(j) == '.' || s.charAt(i) == p.charAt(j)) dp[i+1][j+1] = dp[i][j];
                if(p.charAt(j) == '*'){
                    if(p.charAt(j-1)!=s.charAt(i) && p.charAt(j-1)!='.'){
                        dp[i+1][j+1] = dp[i+1][j-1];//0 of the preceding element.
                    }
                    else{
                        dp[i+1][j+1] = (dp[i+1][j] || dp[i][j+1] || dp[i+1][j-1]);//one
                    }
                }
            }
        }
        return dp[s.length()][p.length()];
    }
}