正则匹配

lc10, *可以匹配0个或者多个前一个字符

 1 class Solution(object):
 2     def isMatch(self, s, p):
 3         """
 4         :type s: str
 5         :type p: str
 6         :rtype: bool
 7         """
 8         m=len(s)+1
 9         n=len(p)+1
10 
11         dp=[[False for j in range(n)] for i in range(m)] 
12         dp[0][0]=True
13 
14         for j in range(1,n):
15             if(j>=2 and p[j-1]=="*" and dp[0][j-2]==True ):
16                 dp[0][j]=True
17 
18         for i in range(1,m):
19             for j in range(1,n):
20                 if(s[i-1]==p[j-1] or p[j-1]=="."):
21                     dp[i][j]=dp[i-1][j-1]
22                 elif p[j-1]=="*":
23                     if(s[i-1]!=p[j-2] and p[j-2]!="."):
24                         dp[i][j]=dp[i][j-2]
25                     else:
26                         dp[i][j]=dp[i][j-2] or dp[i][j-1] or dp[i-1][j]
27         
28         return dp[-1][-1]

lc44 *可以匹配任意字符串

 1 class Solution(object):
 2     def isMatch(self, s, p):
 3         """
 4         :type s: str
 5         :type p: str
 6         :rtype: bool
 7         """
 8         m=len(s)+1
 9         n=len(p)+1
10 
11         dp=[[False for j in range(n)] for i in range(m)]
12         dp[0][0]=True
13 
14         for j in range(1,n):
15             if (p[j-1]=='*' and dp[0][j-1]==True):
16                 dp[0][j]=True
17         
18         for i in range(1,m):
19             for j in range(1,n):
20                 if(s[i-1]==p[j-1] or p[j-1]=='?'):
21                     dp[i][j]=dp[i-1][j-1]
22                 elif p[j-1]=="*":
23                             # *表示空字符时； *表示任意字符，
24                     dp[i][j]=dp[i][j-1] or dp[i-1][j]
25 
26         return dp[-1][-1]