10-正则表达式
10-正则表达式
10. 正则表达式匹配
定义状态
- 定义动态数组
(n为字符串p的长度+1,m为字符串s的长度+1) - 为什么要加1
- 因为我们还要处理空字符串的情况,比如p为空,s为空,或者p为空,s不为空
的含义:p的前 个字符能否匹配s的前 个字符- 为什么是n-1和m-1?
- 因为动态数组里面加了一列和一行空字符的匹配情况,故需要-1才能对应相应字符串
因此创建好的dp数组如下图:
确定动态转移方程
说明:为了区别dp数组与字符串索引的区别(因为相差1),我们设
有以下几种情况是需要我们处理的:
- 当
(即正好能够匹配或者相对应的是一个 )
那么我们只需要看一下前面
即状态转移方程为
当 $p[j] ==’‘
$)两种情况分别对应的处理方式为:
如果
的前一个字符正好对应了 ,状态转移过程为:如果是
的前一个字符为 那么只需看 的前面字符匹配情况,状态转移过程为:
边界:
首先我们要确定
,当p为空,s为空时,肯定匹配成功。那么当 p 为空字符串,而s不为空时,dp数组必定为False,正好初始化dp数组的时候设置的是False;即dp数组的第一列为False可以确定
当s为空字符串,而p不为空时,我们无需判断p里面的第一个值是否为””,如果为””,那肯定匹配不到为Fasle,原数组正好是Fasle,所以直接从2开始判断即可。如果遇到了*,只要判断其对应的前面两个元素的dp值
java
1 | class Solution { |
评论
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Coding-Zuo!