Regular Expression Matching
題目是要求寫出包含 '.' '*'和英文字母的正則表達式匹配方案

lintcode把這題放在DFS下面，做的我頭都大了，后來看了下別人的做法，dp就很明顯了

首先建立二維boolean array dp[s.length+1][p.length+1]，代表s的第幾個字符和p的第幾個字符是否達到匹配

首先dp[0][0] = true， 以及dp[i][0]都為false

然后對dp[0][j] 進行初始化，可知存在“*”的情況，所以要對這個處理下

然后兩個for loop， 分別是對i j 的匹配關(guān)系

如果遍歷到的p[j] 是'.' 或者等于s[i]，那么此時dp[i+1][j+1] = dp[i][j]

如果遍歷到的是'*'， 那么分以下情況考慮

1. 如果p[j-1] 不是'.'或者和s[i]不相等，那么此時的‘*’作用就是消掉p[j-1], 此時
   dp[i+1][j+1] = dp[i+1][j-1] 讓p[j-2]嘗試匹配s[i]
2. 如果是相等或者是'.'的情況，那么就是說明前面一位匹配到了
   則有下面三種情況，
   dp[i+1][j+1] = dp[i][j+1] 說明a* 中匹配到了多個a
   dp[i+1][j+1] = dp[i+1][j] 說明a* 匹配到了一個a
   dp[i+1][j+1] = dp[i+1][j-1]說明a*匹配到了0個a

代碼如下

public class Solution {
    /**
     * @param s: A string 
     * @param p: A string includes "." and "*"
     * @return: A boolean
     */
    public boolean isMatch(String s, String p) {
       if (s == null || p == null) {
        return false;
    }
       boolean[][]dp = new boolean[s.length() + 1][p.length() + 1];
       char[]ss = s.toCharArray();
       char[]pp = p.toCharArray();
       dp[0][0] = true;
       for(int i = 0; i < pp.length; i++){
           if (pp[i] == '*' && (i > 0 && dp[0][i-1])) {
            dp[0][i+1] = true;
        }
       }
       
       for(int i = 0; i < ss.length; i++){
           for(int j = 0; j < pp.length; j++){
               if(pp[j] == '*' && j > 0){
                   if(pp[j - 1] != ss[i] && pp[j - 1] != '.'){
                       dp[i + 1][j + 1] = dp[i+1][j-1];
                      
                   }else{
                       dp[i +1][j + 1] = (dp[i + 1][j] || dp[i][j+1]||dp[i+1][j-1]);
                   }
               }
               
               if(pp[j] == '.' || pp[j] == ss[i]){
                   dp[i + 1][j + 1] = dp[i][j];
               }
           }
       }
       return dp[ss.length][pp.length];
    }

}