- "p"的第一个字符为"*"；
- 边缘条件，s 或者 p 为空；
- 填充table。p=="*"(either 0 or match 1, match more than one can be reduced to match 1)； p != "*"；
public class Solution {
public boolean isMatch(String s, String p) {
if(p.charAt(0)=='*') return false;
boolean M[][] = new boolean[s.length()+1][p.length()+1];
// s is empty:
M[0][0] = true;
for(int j=1; j<=p.length(); j++) {
M[0][j] = p.charAt(j-1)=='*' && M[0][j-2];
}
// p is empty:
for(int i=1; i<=s.length(); i++) {
M[i][0] = false;
}
// fill the table:
for(int i=1; i<=s.length(); i++) {
for(int j=1; j<=p.length(); j++) {
if(p.charAt(j-1) != '*') {
M[i][j] = ((p.charAt(j-1) == s.charAt(i-1)) || (p.charAt(j-1) == '.')) && M[i-1][j-1];
} else {
M[i][j] = M[i][j-2] || ((p.charAt(j-2)==s.charAt(i-1) || p.charAt(j-2)=='.') && M[i-1][j]);
}
}
}
return M[s.length()][p.length()];
}
}
