Put these two questions together (Wildcard Matching & Regular Expression Matching)

• Actually the `DP` solution of these two question are quite similar. It's more like `reverse the strings` and we can get a same solution for one question from another.

Below some different solutions for these two questions.

First, the `DP` solution. - 44. Wildcard Matching

``````public class Solution {
public boolean isMatch(String s, String p) {
int slen = s.length(), plen = p.length();
boolean[][] dp = new boolean[slen + 1][plen + 1];
dp[slen][plen] = true;
for (int j = plen - 1; j >= 0; j--) {
dp[slen][j] = p.charAt(j) == '*' && dp[slen][j + 1];
}

/*
if p.charAt(j) == '*', dp[i][j] = true, if:
1. match zero element, dp[i][j + 1];
2. match at least one element, dp[i + 1][j]
*/
for (int i = slen - 1; i >= 0; i--) {
for (int j = plen - 1; j >= 0; j--) {
if (p.charAt(j) != '*') {
dp[i][j] = dp[i + 1][j + 1] && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '?');
} else {
dp[i][j] = dp[i][j + 1] || dp[i + 1][j];
}
}
}
return dp[0][0];
}
}
``````

And the `DP` solution for 10. Regular Expression Matching.

``````public class Solution {
public boolean isMatch(String s, String p) {
int slen = s.length(), plen = p.length();
boolean[][] dp = new boolean[slen + 1][plen + 1];
dp[0][0] = true;
// matches the empty string
for (int j = 1; j <= plen; j++) {
dp[0][j] = j > 1 && dp[0][j - 2] && p.charAt(j - 1) == '*';
}
/* When p[j - 1] == '*', dp[i][j] = true
if:
1. match zero element, dp[i][j - 2]
2 . match at least one element, dp[i - 1][j] && s[i - 1] matches p[j - 2]
*/
for (int i = 1; i <= slen; i++) {
for (int j = 1; j <= plen; j++) {
if (p.charAt(j - 1) != '*') {
dp[i][j] = dp[i - 1][j - 1] && (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.');
} else {
dp[i][j] = dp[i][j - 2] || (dp[i - 1][j] && (s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.'));
}
}
}
return dp[slen][plen];
}
}
``````

Besides, this is the recursion solution for 10. Regular Expression Matching, from here.

``````public class Solution {
public boolean isMatch(String s, String p) {
if (p.length() == 0) return s.length() == 0;
if (p.length() == 1) return s.length() == 1 && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.');
if (p.charAt(1) == '*') {
return isMatch(s, p.substring(2)) || (s.length() > 0 && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.')) && isMatch(s.substring(1), p);
} else {
if (s.length() == 0) return false;
return (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.') ? isMatch(s.substring(1), p.substring(1)) : false;
}
}
}
``````

And this is the greedy algorithm for 44. Wildcard Matching, from here.

``````public class Solution {
public boolean isMatch(String s, String p) {
int i = 0, j = 0, match = 0, star = -1;
while (i < s.length()) {
if (j < p.length() && (p.charAt(j) == '?' || p.charAt(j) == s.charAt(i))) {
i++;
j++;
continue;
}
if (j < p.length() && p.charAt(j) == '*') {
match = i;
star = j++;
continue;
}
if (star >= 0) {
i = ++match;
j = star + 1;
continue;
}
return false;
}
while (j < p.length()) {
if (p.charAt(j++) != '*') return false;
}
return true;
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.