My python solution (104ms)


  • 2
    H
    class Solution:
        def isMatch(self, s, p):
        	dp=[[False for x in range(len(p)+1)] for x in range(len(s)+1)]
        	dp[0][0]=True
        	for j in range(0,len(p)):
        		if p[j]=='*':
        			dp[0][j+1]=dp[0][j-1]
        	for i in range(0,len(s)):
        		for j in range(0,len(p)):
        			if p[j]=='*':
        				if dp[i+1][j-1]:
        					dp[i+1][j+1]=True
        				elif dp[i][j+1] and (p[j-1]=='.' or s[i]==p[j-1]):
        					dp[i+1][j+1]=True	   			
        			else:
        				if dp[i][j]==True and (s[i]==p[j] or p[j]=='.'):
        					dp[i+1][j+1]=True
        	return dp[len(s)][len(p)]

  • 0
    I

    Can you explain what is going on? I don't understand.


Log in to reply
 

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