10. Regular Expression Matching
class Solution {
public boolean isMatch(String s, String p) {
if (s == null || p == null) {
return false;
}
boolean[][] match = new boolean[s.length() + 1][p.length() + 1];
match[0][0] = true;
for (int i = 1; i < p.length() + 1; i++) {
if (p.charAt(i - 1) == '*') {
match[0][i] = match[0][i - 2];
}
}
for (int i = 1; i < s.length() + 1; i++) {
for (int j = 1; j < p.length() + 1; j++) {
if (s.charAt(i - 1) == p.charAt(j - 1)) {
match[i][j] = match[i - 1][j - 1];
} else if (p.charAt(j - 1) == '.') {
match[i][j] = match[i - 1][j - 1];
} else if (p.charAt(j - 1) == '*') {
if (p.charAt(j - 2) == '.' || p.charAt(j - 2) == s.charAt(i - 1)) {
match[i][j] = match[i][j - 2] || match[i - 1][j];
} else {
match[i][j] = match[i][j - 2];
}
}
}
}
return match[s.length()][p.length()];
}
}