正则表达式匹配
正则表达式匹配
LeetCode-10. 正则表达式匹配匹配,题目内容如下:
1 |
|
由于题目是要求以正则串来匹配,那么我们以正则串为主,根据正则串的每个字符选择相应的策略来匹配需要匹配的字符串。题解中给出的是正则表达式匹配题解。关于动态规划算法,是一个比较难以理解的算法,通过查阅资料和习题练习,有助于掌握动态规划算法的思想。学习动态规划之前不能一蹴而就,直接上手动态规划,应该从简单的开始,斐波那契数列就是一个很好的例子,最开始使用递归,然后分析递归中的每一个步骤,可以发现很多步骤都是重复计算的过程,因此进行优化,变成记忆化+递归,然后再尝试去转换成动态规划。
回到这道题本身,我们在匹配的时候,先以最简单的问题开始,不考虑特殊规则时,是逐字匹配。以匹配串和正则串为x轴和y轴,建立一个二维数组,每一个字符互相对应一个格子,如果某个字母与上面的能够匹配上,并且前面的串已经匹配成功,因此前面的串加上这个字符仍然能够完全匹配。以最简单的两个单字符匹配为例,如图:
起始状态设置为空串,两个空串是能够匹配的,因此第一个位置是 true
,而空串不能够与任意字符匹配,因此第一行与第一列的其他均为false
。那么在匹配当前字符时,发现这两个字符相同,并且这两个字符之前的串是完全匹配的,即dp[i - 1][j - 1] && s.charAt(i - 1) == p.charAt(j - 1)
,因此在上图留空的位置应该为 true
,所以a == a
,答案显而易见,但是我们可以通过这样的思路来解决正则表达式匹配的问题。
不难发现,这个动态规划的二维数组里面存储的是s
串中前i
项与p
串中前j
项是否可以匹配,这就是动态规划中的状态。接下来我们需要通过题设的条件,找出根据前面状态计算后面状态的方法,这种方法即是状态转移方程。剩下的就是处理动态规划的边界值问题了。
在这道题中通过前面的分析,再对题设条件找出对应的几种情况的状态转移方程。
.
能够匹配任意单个字符,那么遇到这个符号,都属于可以匹配,因此这个符号为必定匹配,将其归至其他匹配的判断中。*
的情况需要考虑两个因素,前一个字符不匹配的情况和多个字符匹配的情况。首先考虑前一个字符不匹配,那么有了这个星号,只要前面的是匹配的,则这个不匹配字符可以忽略,即dp[i][j - 2]
。考虑多个字符匹配的情况,s
串中的当前字符与p
串星号前一个字符匹配,并且s
串中前面的串或者前一个字符能够匹配上,则这个字符也能匹配,即dp[i - 1][j] || dp[i][j - 2]
。
看到这里,不了解动态规划的人可能已经懵逼了,因为动态规划常常需要一些经验才能很好的运用,具体实现代码如下:
1 |
|
学习到现在,对动态规划有了一定的了解,也能够大概的分析出状态,但是在具体实现过程中仍然存在一定的困难,需要通过题解的帮助才能完成解答。接下来需要逐渐减少对题解的依赖,独立完成动态规划题目的分析和实现。