BiruLyu
7/31/2017 - 12:18 AM

## 10. Regular Expression Matching(#DP).java

``````public class Solution {
public boolean isMatch(String s, String p) {
return p.isEmpty() ?
s.isEmpty() :
p.length() > 1 && p.charAt(1) == '*' ?
isMatch(s, p.substring(2)) ?
true :
s.isEmpty() || (s.charAt(0) != p.charAt(0) && p.charAt(0) != '.') ?
false :
isMatch(s.substring(1), p) :
s.isEmpty() || (s.charAt(0) != p.charAt(0) && p.charAt(0) != '.') ?
false :
isMatch(s.substring(1), p.substring(1));
}
}``````
``````public class Solution {
public boolean isMatch(String s, String p) {
for(int i = 0; i < p.length(); s = s.substring(1)) {
char c = p.charAt(i);
if(i + 1 >= p.length() || p.charAt(i + 1) != '*')
i++;
else if(isMatch(s, p.substring(i + 2)))
return true;

if(s.isEmpty() || (c != '.' && c != s.charAt(0)))
return false;
}

return s.isEmpty();
}
}``````
``````public class Solution {
public boolean isMatch(String s, String p) {

if (s == null || p == null) {
return false;
}
boolean[][] dp = new boolean[s.length()+1][p.length()+1];
dp[0][0] = true;
for (int i = 0; i < p.length(); i++) {
if (p.charAt(i) == '*' && dp[0][i-1]) {
dp[0][i+1] = true;
}
}
for (int i = 0 ; i < s.length(); i++) {
for (int j = 0; j < p.length(); j++) {
if (p.charAt(j) == '.') {
dp[i+1][j+1] = dp[i][j];
}
if (p.charAt(j) == s.charAt(i)) {
dp[i+1][j+1] = dp[i][j];
}
if (p.charAt(j) == '*') {
if (p.charAt(j-1) != s.charAt(i) && p.charAt(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]);
}
}
}
}
return dp[s.length()][p.length()];
}
}``````