【刷题记录】10. 正则表达式匹配
一、题目描述
来源:力扣(LeetCode)
给你一个字符串 s 和一个字符规律 p,请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素所谓匹配,是要涵盖 整个字符串 s 的,而不是部分字符串。
示例 1:
示例 2:
示例 3:
提示:
1 <= s.length <= 20
1 <= p.length <= 30
s 只包含从 a-z 的小写字母。
p 只包含从 a-z 的小写字母,以及字符 . 和 *。保证每次出现字符 * 时,前面都匹配到有效的字符
二、思路分析
这个题目我可以利用动态规划的思想来解决:
首先我们定义
dp[i][j]
表示 s 的前 i 个是否能被 p 的前 j 个匹配如果
p
的第j
个字符是一个字母如果
s
的第i
个字符与p
的第j
个字符不相同,那么无法进行匹配,不符合了。如果前面的都匹配的同时,且
s
的第i
个字符与p
的第j
个字符相同,即dp[i-1][j-1] = dp[i,j] && s[i]=p[j]
如果
p
的第j
个字符是*
, 那么我们就是对 前面一个字符p[j-1]
就行任意次数的匹配0 次就是 dp[i][j] == dp[i][j-2]
1 次就是 dp[i][j] == dp[i−1][j−2] && s[i] == p[j-1]
2 次就是 dp[i][j] == dp[i−2][j−2] && s[i-1]s[i] == p[j-1]
....总结就是 $dp[i,j]=\begin{cases}dp[i][j-2] ,when & s[i] \neq p[j-1] \dp[i−1][j] or dp[i][j−2],when & s[i]==p[j−1] \\end{cases}$
如果
p[j]
为'.'
:匹配的条件是前面的字符匹配,s
中的第i
个字符可以是任意字符。即dp[i,j] = dp[i - 1, j - 1] && p[j] == '.'
。动态规划的边界条件为 ,即两个空字符串是可以匹配的。最终的答案即为 ,其中
m
和n
分别是字符串s
和p
的长度
三、代码实现
复杂度分析
复杂度分析
时间复杂度:,其中
m
和n
分别是字符串s
和p
的长度,每个状态在进行转移时的时间复杂度为 。空间复杂度:,存储所有状态使用的空间。
运行结果
总结
这道题的重点是 动态规划 的运用
而动态规划的解题核心主要分为两步:
第一步:状态的定义
第二步:状态转移方程的定义
状态表示的是我们在求解问题之中,对问题的分析和转化
运用动态规划我们将一个大问题转化成几个小问题,求解小问题,然后推出大问题的解
版权声明: 本文为 InfoQ 作者【WangNing】的原创文章。
原文链接:【http://xie.infoq.cn/article/61eae62649112ca62ea3bac8c】。
本文遵守【CC-BY 4.0】协议,转载请保留原文出处及本版权声明。
评论