坪山网站建设资讯,齐河网站建设费用,市场营销论文,天睦和生态建设有限公司网站摘要
剑指 Offer 19. 正则表达式匹配
请实现一个函数用来匹配包含. 和*的正则表达式。模式中的字符.表示任意一个字符#xff0c;而*表示它前面的字符可以出现任意次#xff08;含0次#xff09;。在本题中#xff0c;匹配是指字符串的所有字符匹配整个模式。例如#x…摘要
剑指 Offer 19. 正则表达式匹配
请实现一个函数用来匹配包含. 和*的正则表达式。模式中的字符.表示任意一个字符而*表示它前面的字符可以出现任意次含0次。在本题中匹配是指字符串的所有字符匹配整个模式。例如字符串aaa与模式a.a和ab*ac*a匹配但与aa.a和ab*a均不匹配。
一、动态规划解析
假设主串为A模式串为B从最后一步出发需要关注最后进来的字符。假设A的长度为n B的长度为m 关注正则表达式B 的最后一个字符是谁它有三种可能正常字符、∗ 和 .点那针对这三种情况讨论即可如下
如果B的最后一个字符是正常字符那就是看 A[n−1]是否等于 B[m−1]相等则看A0..n−2与 B0..m−2不等则是不能匹配这就是子问题。如果B的最后一个字符是.它能匹配任意字符直接看 A0..n−2与B0..m−2。如果B的最后一个字符是*它代表 B[m−2]c可以重复0次或多次它们是一个整体 c∗ 情况一A[n−1]是0个cB最后两个字符废了能否匹配取决于 A0..n−1和 B0..m−3是否匹配。 情况二A[n−1]是多个c中的最后一个这种情况必须 A[n−1]c或者 c′.’所以A匹配完往前挪一个B继续匹配因为可以匹配多个继续看 A0..n−2和 B0..m−1是否匹配。
转移方程
f[i][j]代表A 的前i个和B的前j个能否匹配
对于前面两个情况可以合并成一种情况 f[i][j]f[i−1][j−1]对于第三种情况对于c∗分为看和不看两种情况 不看直接砍掉正则串的后面两个 f[i][j]f[i][j−2] 看正则串不动主串前移一个f[i][j]f[i−1][j]
初始条件
特判需要考虑空串空正则
空串和空正则是匹配的f[0][0]true空串和非空正则不能直接定义true和false必须要计算出来。比如A ,Ba∗b∗c∗ 非空串和空正则必不匹配f[1][0]...f[n][0]false 非空串和非空正则那肯定是需要计算的了。
大体上可以分为空正则和非空正则两种空正则也是比较好处理的对非空正则我们肯定需要计算非空正则的三种情况前面两种可以合并到一起讨论第三种情况是单独一种那么也就是分为当前位置是∗和不是∗两种情况了。我们开数组要开n1这样对于空串的处理十分方便。结果就是 f[n][m]。
package DP;/*** Classname JZ19正则表达式匹配* Description TODO* Date 2023/3/3 19:42* Created by xjl*/
public class JZ19正则表达式匹配 {public boolean isMatch(String A, String B) {int n A.length();int m B.length();boolean[][] f new boolean[n 1][m 1];for (int i 0; i n; i) {for (int j 0; j m; j) {//分成空正则和非空正则两种if (j 0) {f[i][j] i 0;} else {//非空正则分为两种情况 * 和 非*if (B.charAt(j - 1) ! *) {if (i 0 (A.charAt(i - 1) B.charAt(j - 1) || B.charAt(j - 1) .)) {f[i][j] f[i - 1][j - 1];}} else {//碰到 * 了分为看和不看两种情况//不看if (j 2) {f[i][j] | f[i][j - 2];}//看if (i 1 j 2 (A.charAt(i - 1) B.charAt(j - 2) || B.charAt(j - 2) .)) {f[i][j] | f[i - 1][j];}}}}}return f[n][m];}
}博文参考
《leetcode》
