标准模块 re
补上’$’,确保match函数用p匹配整个s.
import re
class Solution(object):
def isMatch(self, s, p):
return re.match(p+'$',s)
DFS
class Solution(object):
def isMatch(self, s, p):
sd, pd = len(s), len(p)
def dfs(si, pi):
if pi == pd:
return si == sd # 正则串结束时, 匹配串也要结束
match = si < sd and (s[si] == p[pi] or p[pi]
== '.') # 匹配串还有, 且当前位置两串字符相同
if pi+1 < pd and p[pi+1] == '*': # 是否存在*
return dfs(si, pi+2) or (match and dfs(si+1, pi)) # 不匹配 or 匹配
return match and dfs(si+1, pi+1)
return dfs(0, 0)
DP
dp[i][j] : s[:i]与p[:j]是否匹配.
-
初始化
因为 s[:0] == p[:0] == ‘’ , 必定匹配, 所以 dp[0][0] = True .
由于 ‘*‘ 的存在, s[:0]==’‘ 可能与 p[:j] 匹配, 因为 ‘*‘ 出现在首位没有意义, 所以 j 从 2 开始. -
状态转移
- if p[j-1] == s[i-1] or p[j-1] == ‘.’
匹配成功, dp[i][j] = dp[i-1][j-1] . - elif p[j-1] == ‘*‘
出现元字符 ‘*‘- if p[j-2] == s[i-1] or p[j-2] == ‘.’
匹配0个时: dp[i][j] = dp[i][j-2]
匹配1~n个时: dp[i][j] = dp[i-1][j] - else
匹配0个时: dp[i][j] = dp[i][j-2]
- if p[j-2] == s[i-1] or p[j-2] == ‘.’
- if p[j-1] == s[i-1] or p[j-1] == ‘.’
class Solution(object):
def isMatch(self, s, p):
def isMatch(self, s, p):
dp = [[False]*(len(p)+1) for _ in range(len(s)+1)]
dp[0][0] = True
for j in range(2, len(p)+1):
if p[j-1] == '*':
dp[0][j] = dp[0][j-2]
for i in range(1, len(s)+1):
for j in range(1, len(p)+1):
if p[j-1] == s[i-1] or p[j-1] == '.':
dp[i][j] = dp[i-1][j-1]
elif p[j-1] == '*':
dp[i][j] = dp[i][j-2]
if p[j-2] == s[i-1] or p[j-2] == '.':
dp[i][j] |= dp[i-1][j]
return dp[-1][-1]