# Java DP Accepted

• ``````public class Solution {
public boolean isMatch(String s, String p) {
int m = s.length(), n = p.length();
char[] ws = s.toCharArray();
char[] wp = p.toCharArray();
boolean[][] dp = new boolean[m+1][n+1];
dp[0][0] = true;
for (int j = 1; j <= n; j++)
dp[0][j] = dp[0][j-1] && wp[j-1] == '*';
for (int i = 1; i <= m; i++)
dp[i][0] = false;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (wp[j-1] == '?' || ws[i-1] == wp[j-1])
dp[i][j] = dp[i-1][j-1];
else if (wp[j-1] == '*')
dp[i][j] = dp[i-1][j] || dp[i][j-1];
}
}
return dp[m][n];
}
}``````

• My python DP solution is same idea as yours and it got TLE, I am not sure why...? Can you spot any difference?

``````class Solution(object):
def isMatch(self, s, p):
"""
:type s: str
:type p: str
:rtype: bool
"""
n, m = len(s), len(p)

match = [[False for i in xrange(m + 1)] for j in xrange(n + 1)]
match[0][0] = True

for j in xrange(1, m + 1):
if p[j - 1] == '*':
match[0][j] = match[0][j - 1]

for i in xrange(1, n + 1):
for j in xrange(1, m + 1):
if p[j - 1] == '?' or p[j - 1] == s[i - 1]:
match[i][j] = match[i - 1][j - 1]

if p[j - 1] == '*':
match[i][j] = match[i][j - 1] or match[i - 1][j]

return match[-1][-1]``````

• @IWantToPass I tried the similar approach in Python just as you did and observed the Time Limit Exceeded problem. Don't know where the problem lies.

Anyway the running time is O(mn) and space O(mn).

• @IWantToPass I got the same problem. TLE on Python DP

• What does DP stand for?

• @colas dynamic programming

• ``````else if (wp[j-1] == '*')
dp[i][j] = dp[i-1][j] || dp[i][j-1];
``````

I have a question here. I think here we should add

``````else if (wp[j-1] == '*')
dp[i][j] = dp[i-1][j] || dp[i][j-1] || dp[i-1][j-1];
``````

because * can be ? in some cases.

• for (int i = 1; i <= m; i++)
dp[i][0] = false;

These code is no needed, because the default value of boolean array is false.

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