文章目录
1. 题目2. 解题思路3. 代码实现3.1 回溯3.2 动态规划
4. 总结5. 参考文献
1. 题目
请实现一个函数用来匹配包含’.‘和’‘的正则表达式。模式中的字符’.‘表示任意一个字符，二’'表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"abaca"匹配，但与"aa.a"和"ab*a"均不匹配。
2. 解题思路
不说了直接向大佬学习吧！ 详解 回溯+动态规划
3. 代码实现
3.1 回溯
class Solution:
def isMatch(self
, s
: str, p
: str) -> bool:
if not p
: return not s
first_match
= bool(s
and p
[0] in {s
[0],'.'})
if len(p
) >= 2 and p
[1] == "*":
return self
.isMatch
(s
, p
[2:]) or \
first_match
and self
.isMatch
(s
[1:], p
)
else:
return first_match
and self
.isMatch
(s
[1:], p
[1:])
3.2 动态规划
class Solution:
def isMatch(self
, s
: str, p
: str) -> bool:
if not p
: return not s
if not s
and len(p
) == 1: return False
m
, n
= len(s
) + 1, len(p
) + 1
dp
= [[False for _
in range(n
)] for _
in range(m
)]
dp
[0][0] = True
dp
[0][1] = False
for c
in range(2, n
):
j
= c
- 1
if p
[j
] == '*':
dp
[0][c
] = dp
[0][c
- 2]
for r
in range(1,m
):
i
= r
- 1
for c
in range(1, n
):
j
= c
- 1
if s
[i
] == p
[j
] or p
[j
] == '.':
dp
[r
][c
] = dp
[r
- 1][c
- 1]
elif p
[j
] == '*':
if p
[j
- 1] == s
[i
] or p
[j
- 1] == '.':
dp
[r
][c
] = dp
[r
- 1][c
] or dp
[r
][c
- 2]
else:
dp
[r
][c
] = dp
[r
][c
- 2]
else:
dp
[r
][c
] = False
return dp
[m
- 1][n
- 1]
4. 总结
伤不起
5. 参考文献
[1] 剑指offer丛书 [2] 剑指Offer——名企面试官精讲典型编程题
