# Python DP & BackTracking

• First to try once DP very similar to 10 Regular Expression Matching, actually TLE before using this piece of code, which I got from other folks of the discuss:

``````        count = 0
for i in xrange(len(p)):
if p[i] != '*':
count += 1
if count > len(s):
return False
``````

Even if it seems a hacky way to cheat the OJ, but at least allow me post the less efficient "solution" here:

``````class Solution(object):
def isMatch(self, s, p):
count = 0
for i in xrange(len(p)):
if p[i] != '*':
count += 1
if count > len(s):
return False
dp = [ [False for i in xrange(len(p) + 1)] for j in xrange(len(s) + 1) ]
dp[0][0] = True
for i in xrange(len(p)):
if p[i] == '*':
dp[0][i + 1] = True
else:
break
for i in xrange(len(s)):
for j in xrange(len(p)):
if p[j] != '*':
dp[i + 1][j + 1] = (s[i] == p[j] or p[j] == '?') and dp[i][j]
else:
dp[i + 1][j + 1] = dp[i + 1][j] or dp[i][j] or dp[i][j + 1]
return dp[-1][-1]
``````

Then will be the back-tracking solution, the basic idea is that when there is a miss match, go back to the pre-nearest '*' and move one step more of s.

``````class Solution(object):
def isMatch(self, s, p):
idxs, idxp, rs, rp = 0, 0, -1, -1
while idxs < len(s):
if idxp < len(p):
if s[idxs] == p[idxp] or p[idxp] == '?':
idxs, idxp = idxs + 1, idxp + 1
elif p[idxp] == '*':
idxp, rp, rs = idxp + 1, idxp + 1, idxs + 1
else:
if rs == -1:
return False
idxs, idxp, rs = rs, rp, rs + 1
else:
if rs == -1:
return False
idxs, idxp, rs = rs, rp, rs + 1
while idxp < len(p) and p[idxp] == '*':
idxp += 1
return idxp == len(p)
``````

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