# Python AC solution beats 94.18%

• Details to how DP works is already covered in great detail in other posts and I shan't repeat them here.

Key to my solution:

I split the pattern string into 2 arrays, this facilitates the ready reuse of solution in wildcard matching without considering much for s[j-2] due to presence of * characters. (yes I'm lazy)

"a*.bc*d*" -> [ 'a' , '.' , 'b' , 'c' , 'd' ] , [ True, False, False, True, True ]

What modifications from wildcard matching is needed:

• DP array initialization (since any non * character can be nullified with a following *)
• Evaluation for each cell (just some additional booleans with AND)
• ? to .

That's all the needed stuff. (REALLY!)

What's not needed though, is some lines to print the DP array (commented with #) for your reference

class Solution(object):
def isMatch(self, s, p):
#def pbol(boo,t="T",f=" "):
#    return t if boo else f
if not p:
return not s

p2 = [ch for ch in p if ch!='*']
p3 = [(p[i+1]=='*') for i,val in enumerate(p[:-1]) if val!='*']
if p[-1]!='*':
p3.append(False)

dp=[[False for _ in range(len(s)+1)] for _ in range(len(p2)+1)]

t=0
for boo in p3:
if boo:
t+=1
else:
break
for i in range(t+1):
dp[i][0]=True

for i in range(len(p2)):
for j in range(len(s)):
if (not p3[i]) and (p2[i]=='.' or p2[i]==s[j]):
dp[i+1][j+1]=dp[i][j]
if p3[i]:
dp[i+1][j+1]=dp[i][j+1] or (dp[i+1][j] and (p2[i]=='.' or p2[i]==s[j]))
#print("\t {}".format(s))
#for i in range(len(p2)+1):
#    print("{}{}\t{}".format( pbol(i,p2[i-1],""), pbol(i,pbol(p3[i-1]),""), "".join(pbol(bol) for bol in dp[i]) ))
return dp[len(p2)][len(s)]

P.S. Above is my first submitted and accepted solution. Attempting to optimize it by caching the least possible j value gave me a WA submission and turns out performing EXACTLY the same. Micro-optimization is the root of all evil :(

class Solution(object):
def isMatch(self, s, p):
"""
:type s: str
:type p: str
:rtype: bool
"""
#rewrite with DP
#simplify string
#def pbol(boo,t="T",f=" "):
#    return t if boo else f
if not p:
return not s

p2 = [ch for ch in p if ch!='*']
p3 = [(p[i+1]=='*') for i,val in enumerate(p[:-1]) if val!='*']
if p[-1]!='*':
p3.append(False)

#PS
dp=[[False for _ in range(len(s)+1)] for _ in range(len(p2)+1)]

t=0
for boo in p3:
if boo:
t+=1
else:
break
for i in range(t+1):
dp[i][0]=True

t2=0
#print("\n\t {}".format(s))
#print("\t{} {}".format("".join(pbol(bol) for bol in dp[0]), t))
for i in range(len(p2)):
buf = False
for j in range(t2,len(s)):
if (not p3[i]) and (p2[i]=='.' or p2[i]==s[j]):
dp[i+1][j+1]=dp[i][j]
if p3[i]:
dp[i+1][j+1]=dp[i][j+1] or (dp[i+1][j] and (p2[i]=='.' or p2[i]==s[j]))
if not buf and dp[i+1][j+1]:
buf = True
if i>=t and not buf:
t2+=1
#print("{}{}\t{} {}".format(p2[i], pbol(p3[i]), "".join(pbol(bol) for bol in dp[i+1]), t))
return dp[len(p2)][len(s)]

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