# DP solution. O(n) space O(n^2) time

• This is my accepted DP solution. O(n) space. O(n^2) time.
As we need only the previous iteration's result, we can do this DP by using 2 1D arrays instead of a whole 2D matrix.

``````bool isMatch(string s, string p)
{
int n = s.length(), m = p.length();
int i = 0, j = 0;
bool dp[2][10000] = {0};
dp[0][0] = 1;

while(i<m && p[i] == '*')
{
dp[0][i+1] = 1;
i++;
}
int x = 0;
for(i = 1; i <= n; i++)
{
x = x^1;
for(j = 1; j <= m; j++)
{
if(p[j-1] == '*')
dp[x][j] = dp[x^1][j] || dp[x][j-1];
else
dp[x][j] = dp[x^1][j-1] && (s[i-1] == p[j-1] || p[j-1] == '?');
}
dp[x^1][0] = dp[x][0];
}
return dp[x][m];
}``````

• My DP C++ Solution with time complexity O(nm) and space O(nm).Accepted! Time is 302 ms, although kind of embarrassing. The idea is simple. Note

bool isMatch(const char* s, const char* p)
{
int slen = strlen(s), plen = strlen(p);

``````bool **dp = new bool*[slen + 1];
for(int i = 0; i <= slen; i++)
dp[i] = new bool[plen + 1];
dp[0][0] = true;
for(int i = 1; i <= plen; i++)
dp[0][i] = dp[0][i - 1]&&(p[i-1] == '*');
for(int i = 1; i <= slen; i++)
dp[i][0] = false;
for(int i = 1; i <= slen; i++)
{
for(int j = 1; j <= plen; j++)
{
if(p[j-1] != '*')
dp[i][j] = dp[i-1][j-1] && (s[i-1] == p[j-1] || p[j-1] == '?');
else
dp[i][j] = dp[i][j-1] || dp[i-1][j]; //Note here that if p[j-1] == '*', then p[j-1] can either match empty string or match s[i-1] in such case,p[i-1] should keep matching forward.
}
}
bool ret = dp[slen][plen];
for(int i = 0; i <= slen; i++)
delete[] dp[i];
delete[]dp;
return ret;
``````

}

• same solution, but I use vector. It cost 1772 ms. ooooooooooooooooh.

• Thanks! Your 2D-dp solution is very clear! Below is a JAVA version

``````public boolean isMatch_2d_method(String s, String p) {
int m=s.length(), n=p.length();
boolean[][] dp = new boolean[m+1][n+1];
dp[0][0] = true;
for (int i=1; i<=m; i++) {
dp[i][0] = false;
}

for(int j=1; j<=n; j++) {
if(p.charAt(j-1)=='*'){
dp[0][j] = true;
} else {
break;
}
}

for(int i=1; i<=m; i++) {
for(int j=1; j<=n; 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-1][j] || dp[i][j-1];
}
}
}
return dp[m][n];
}``````

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