Here is my O(m*n) solution for this problem.


  • 0
    R

    class Solution:
    def isMatch(self,S,P):
    N=len(S)
    M=len(P)
    S+="?"
    P+="?"
    DP=[[False for i in range(M+1)]for j in range(N+1)]
    DP[N][M]=True

    	for j in range(M-1,-1,-1):#Pattern
    		for i in range(N,-1,-1):#String
    			if P[j]=="*":
    				continue
    			if P[j+1]!="*":
    				if self.isEqual(P[j],S[i]):
    				    if i<N:
    				        DP[i][j]=DP[i+1][j+1]
    			else:
    				if DP[i][j+2]:
    					DP[i][j]=True
    					continue
    				cnt=0
    				while 1:
    					if i+cnt+1>N:
    						break
    					if not self.isEqual(S[i+cnt],P[j]):
    						break
    					if DP[i+1+cnt][j+2]==True:
    						DP[i][j]=True
    						break
    					cnt+=1
    	return DP[0][0]
    def isEqual(self,a,b):
    	if a=="." or b==".":
    		return True
    	else:
    		return True if a==b else False

Log in to reply
 

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