最怕regular Expression的题了。出现regular expression立刻想到几点：
notes：
- 要用到DP/Backtracking;
- 应该是一个2D table， 因为是两个array；
- 边界条件，就是两个String，至少其中一个为空时的情况。
- 两个array并不是同等地位，用后一个match前一个，所以边界条件不相同要分别考虑。
- 最后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];
}
}
