# Python DP solution

• ``````class Solution:
# @return a boolean
def isMatch(self, s, p):
length = len(s)
if len(p) - p.count('*') > length:
return False
dp = [True] + [False]*length
for i in p:
if i != '*':
for n in reversed(range(length)):
dp[n+1] = dp[n] and (i == s[n] or i == '?')
else:
for n in range(1, length+1):
dp[n] = dp[n-1] or dp[n]
dp[0] = dp[0] and i == '*'
return dp[-1]
``````

dp[n] means the substring s[:n] if match the pattern i

dp[0] means the empty string '' or s[:0] which only match the pattern '*'

use the reversed builtin because for every dp[n+1] we use the previous 'dp'

``````public boolean isMatch(String s, String p) {
int count = 0;
for (char c : p.toCharArray()) {
if (c == '*')
count++;
}
if (p.length() - count > s.length())
return false;
boolean[][] dp = new boolean[p.length() + 1][s.length() + 1];
dp[0][0] = true;
for (int j = 1; j <= p.length(); j++) {
char pattern = p.charAt(j - 1);
dp[j][0] = dp[j - 1][0] && pattern == '*';
for (int i = 1; i <= s.length(); i++) {
char letter = s.charAt(i - 1);
if (pattern != '*') {
dp[j][i] = dp[j - 1][i - 1] && (pattern == '?' || pattern == letter);
} else
dp[j][i] = dp[j][i - 1] || dp[j - 1][i];
}
}
return dp[p.length()][s.length()];
}``````

• This post is deleted!

• This is very great! inspired by yours version.

``````def isMatch(self, s, p):
m = len(s)
n = len(p)

if n == 0 and m == 0:
return True
if n == 0 and m != 0:
return False
if p.count('*') == len(p):
return True
if len(p) - p.count('*') > m:
return False

dp = [True] + [False]*m
for cp in p:
if cp != '*':
for i in xrange(m, 0, -1): # m, m-1, .. 1
dp[i] = dp[i-1] and (cp=='?' or s[i-1] == cp)
else:
for i in xrange(1, m+1):
dp[i] = dp[i] or dp[i-1]
dp[0] = dp[0] and cp=='*'

return dp[m]``````

• Golang version:

``````func isMatch(s string, p string) bool {

dp := make([][]bool, len(p) + 1)
for i,_:=range dp {
dp[i] = make([]bool, len(s) + 1)
for j, _:= range dp[i] {
dp[i][j] = false
}
}

dp[0][0] = true

for j:=1; j<=len(p); j++ {
pattern := p[j-1]
dp[j][0] = dp[j-1][0] && pattern == '*'
for i:=1; i<=len(s); i++ {
letter := s[i-1]
if pattern != '*'{
dp[j][i] = dp[j-1][i-1] && (pattern == '?' || pattern == letter)
} else {
dp[j][i] = dp[j][i-1] || dp[j-1][i]
}
}
}
return dp[len(p)][len(s)]
}
``````

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