# Codes and explains of DP solution using python

• Thanks to @ChuntaoLu 's solution.
Based on his solution I wrote these codes and comments which I think are more understandable and easy-to-read in the first glimpse.
Hope this can help people who has no idea how to start with DP solution

``````class Solution(object):
def isMatch(self, s, p):
p = Solution.removeConsecutive('*', p)
return self.isMatchHelper(s, p)

# a little bit of optimization
@staticmethod
def removeConsecutive(mark, p):
i = 0
while i < len(p):
if i+1 < len(p) and p[i] == mark and p[i+1] == mark:
p = p[0:i] + p[i+1:]
else:
i += 1
return p

def isMatchHelper(self, s, p):
"""
:type s: str
:type p: str
:rtype: bool
"""
DP = [True] + [False for _ in range(len(s))]
for i in range(1, len(p)+1):
next_itr = [DP[0] and p[i-1] == '*'] + [False for _ in range(len(s))]
for j in range(1, len(s)+1):
if p[i-1] == '?':
next_itr[j] = DP[j-1]
elif p[i-1] == '*':
next_itr[j] = DP[j] or next_itr[j-1]
else:
next_itr[j] = DP[j-1] and p[i-1] == s[j-1]
DP = next_itr

return DP[-1]

# For a 2d table, dp[i][j] would mean whether sub-pattern p[:i] matches sub-string s[:j].
# Most tricky part is when the current pattern letter is *, suppose its index is i-1, p[:i] will
# match sub-string s[:j] if p[:i] matches s[:j-1] or p[:i-1] matches s[:j], namely current
# cell value is true if its top or its left is true. Since the current row only depends on the previous
# row, we can use two rolling lists to do the dp instead of a matrix.
#
# so the pseudo code of 2d dp solution would be:

# initial DP[0][:]
# for i = 1:len(p)
#     for j = 1:len(s)
#         if p[i-1] is '?':
#             DP[i][j] = DP[i-1][j-1]
#         if p[i-1] is regular character:
#             DP[i][j] = DP[i-1][j-1] and p[i-1] equals s[j-1]
#         if p[i-1] is '*':
#             DP[i][j] = ( DP[i][j-1]     // since '*' can represent multiple characters
#                         or DP[i-1][j]   // since '*' can represent empty characters
# return DP[end][end]
``````

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