# Python DP solution with detailed comments

• ``````class Solution(object):
def isMatch(self, s, p):
"""
:type s: str
:type p: str
:rtype: bool
"""
#O(NM) time, O(NM) space
n, m = len(s), len(p)
match = [[False for j in xrange(m + 1)] for i in xrange(n + 1)]

#Base cases - empty string matches w/ empty pattern
match[0][0] = True

#empty string to nonempty pattern
for i in xrange(1, m + 1):
if i > 1 and p[i - 1] == '*':
match[0][i] = match[0][i - 2]

#DP cases
for i in xrange(1, n + 1):
for j in xrange(1, m + 1):
#If the string char equals the pattern char or the pattern is a dot,
#there is a match if everything before matches
if p[j - 1] == '.' or p[j - 1] == s[i - 1]:
match[i][j] = match[i - 1][j - 1]
#Star can only match if there is something before the star to match
elif j > 1 and p[j - 1] == '*':
#If the character before the star matches char in the string,
#the star can match 0 of the char before it, or at least 1.
#match[i][j-2] is for matching 0, cause we need to skip the last 2
#characters in the pattern. match[i - 1][j] is for matching 1, cause
#we need to skip 1 character in the string, but keep the entire pattern
if p[j - 2] == s[i - 1] or p[j - 2] == '.':
match[i][j] = match[i][j - 2] or match[i - 1][j]
#If the character before the star does not match the char in the string,
#then the only way to get a match is if the star matches 0 characters
else:
match[i][j] = match[i][j - 2]

return match[n][m]``````

• This post is deleted!

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