10. Regular Expression Matching

最怕regular Expression的题了。出现regular expression立刻想到几点：
notes：

1. 要用到DP/Backtracking;
2. 应该是一个2D table， 因为是两个array；
3. 边界条件，就是两个String，至少其中一个为空时的情况。
4. 两个array并不是同等地位，用后一个match前一个，所以边界条件不相同要分别考虑。
5. 最后dp fill the table，考虑为"*"的情况很重要；

Algorithm 分四步：
step 1: construct a 2D mem table;
step 2: s is empty;
step 3: p is empty;
step 4: fill the table;

和朋友聊天聊了一会，然后回来真让我给写出来了。
填写table的时候想好分类。
如果是“*”的话，可能match 0个，或者1个，match多个的时候和match一个是同样的case；

我的代码：

public class Solution {
    public boolean isMatch(String s, String p) {
        int slen = s.length(), plen = p.length();
        // step 1: construct 2D mem table;
        boolean[][] mem = new boolean[slen+1][plen+1];
        mem[0][0] = true;
        // step 2: "s" is empty;
        for (int i=1; i<=plen; i++) {
            mem[0][i] = (p.charAt(i-1)=='*') && mem[0][i-2];
        }
        // step 3: "p" is empty;
        for (int i=1; i<=slen; i++) {
            mem[i][0] = false;
        }
        // fill the table:
        for (int i=1; i<=slen; i++) {
            for (int j=1; j<=plen; j++) {
                if (p.charAt(j-1) != '*') {
                    mem[i][j] = (p.charAt(j-1)==s.charAt(i-1) || p.charAt(j-1)=='.') && mem[i-1][j-1];
                }
                else {
                    mem[i][j] = (mem[i][j-2]==true || (p.charAt(j-2)==s.charAt(i-1) || p.charAt(j-2)=='.') && mem[i-1][j]==true);
                }
            }
        }
        return mem[slen][plen];
    }
}