AcWing 30. 正则表达式匹配 (剑指OFFER leetcode 10)
2021-05-20 11:31
标签：else mat ++ for 一起 content 忽略 授权 ddr 题目描述 模式中的字符’.’表示任意一个字符，而’*’表示它前面的字符可以出现任意次（含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。 例如，字符串”aaa”与模式”a.a”和”abaca”匹配，但是与”aa.a”和”ab*a”均不匹配。 样例 算法1 AcWing 30. 正则表达式匹配 (剑指OFFER leetcode 10) 标签：else mat ++ for 一起 content 忽略 授权 ddr 原文地址：https://www.cnblogs.com/itdef/p/11299204.html
请实现一个函数用来匹配包括’.’和’*’的正则表达式。输入：
s="aa"
p="a*"
输出:true
很经典的题目 也相当的难。
采用动态规划
dp[i][j] 表示 s[0~i)的字符串与p[0~j)的字符串是否匹配
那么有以下几个转换状态
1 p[j-1] 是字母 而且与 s[i-1] 相等，那么当前dp[i][j]是否匹配就依赖于dp[i-1][j-1]
2 p[j-1] 是. 那么肯定与s[i-1]相等， 当前dp[i][j]是否匹配 就依赖于 dp[i-1][j-1]
情况1 2 类似 可以在代码中一起判断
3 p[j-1] 是 那么根据 表示的前面字母的多次重复还是0次重复 分为两种情况
3.1 如果是0次重复 那么当前的p[j-1] == ‘*’ 和 p[j-2] 都可以忽略不计。 那么 dp[i][j] = dp[i]j-2
3.2 如果是多次重复 那么 p[j-2] 与s[i-1] 相等 或者p[j-2]==’.’ 那么dp[i][j] = dp[i-1][j]class Solution {
public:
vector
文章标题：AcWing 30. 正则表达式匹配 (剑指OFFER leetcode 10)
文章链接：http://soscw.com/index.php/essay/87905.html