# python dp solution

• ``````class Solution(object):
def isMatch(self, s, p):
"""
:type s: str
:type p: str
:rtype: bool
"""

if s == p:
return True

# INITIALIZING

# 2
m = len(s)
# 1
n = len(p)

T = [[False for j in range(n+1)] for i in range(m+1)]

T[0][0] = True

#  Deals with patterns like a* or a*b* or a*b*c*
for i in range(1, n+1):
if p[i-1] == '*':
T[0][i] = T[0][i-2]

if not s:
return T[-1][-1]

s = " "+s
p = " "+p

for i in range(1, m+1):
for j in range(1, n+1):

if s[i] == p[j] or p[j] == '.':
T[i][j] = T[i-1][j-1]

elif p[j] == '*':
if j > 1:
T[i][j] = T[i][j-2]

if s[i] == p[j-1] or p[j-1] == '.':
T[i][j] = T[i][j] or T[i-1][j]
else:
T[i][j]  = False

return T[i][j]

``````

• could you explain the logic behind this please? I am trying to understand but I am having trouble.

what does T[i][j] represent?

if you have a "*", why do you do T[i][j] = T[i][j-2]?

• @dal Hi,
boolean in T[i][j] represents if string[:i] and pattern[:j] is a match. (note I had a empty space appended to the front of both s (string) and p (pattern) so the index is adjusted)

in the case of p[j] == "*", we check T[i][j] = T[i][j-2] to see if pattern[j-1:j+1] could match an empty string.

• @ruhao

got it, thanks

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