淘宝网站策划怎么做,企查查在线查询网页版,大丰网站建设,微商城系统开发商文章目录题目描述思路 代码二刷打卡第十二天#xff5e; 题目描述
拖了超级久的一道题 #xff0c;懒得看正则表达式#xff0c;但是其实和正则表达式相关的地方也不多
思路 代码
参照这篇题解写的#xff0c;dalao属实万物皆可动态规划。主要是…
文章目录题目描述思路 代码二刷打卡第十二天 题目描述
拖了超级久的一道题 懒得看正则表达式但是其实和正则表达式相关的地方也不多
思路 代码
参照这篇题解写的dalao属实万物皆可动态规划。主要是分情况见代码注释的Case主要是 空正则正则表达式为 “” )非空正则 a. 不是 ‘✳️’ 的情况 b. 是 ‘✳️’ 的情况重复 0 次的情况 重复的情况 | 的考虑2.a 和 2.b只要满足其中一个即可‘.的考虑在这个代码里实际上只是相当于一个万用符建议还是得动手画一遍表格来填帮助理解。
class Solution {public boolean isMatch(String s, String p) {// init int m s.length();int n p.length();char[] arr1 s.toCharArray();char[] arr2 p.toCharArray();// dp[i][j] 代表 s 的前 i 个和 p 的前 j 个能否匹配boolean[][] dp new boolean[m 1][n 1];// dp 过程for(int i 0; i m; i) {for(int j 0; j n; j) {// Case 1: 空正则if(j 0) {dp[i][j] (i 0);}// Case 2: 非空正则else {// Case 2.1不是*if(arr2[j - 1] ! *) {// 相等 or 为.的情况直接看左上角的最优子结构if(i 0 (arr1[i - 1] arr2[j - 1] || arr2[j - 1] .)) {dp[i][j] dp[i - 1][j - 1];}}// Case 2.2是*最重要的部分else {// Case 2.2.1不看if(j 2) {// 重复0次相当于直接砍掉最后两个字符dp[i][j] dp[i][j - 2];}// Case 2.2.2看if(i 1 j 2 (arr1[i - 1] arr2[j - 2] || arr2[j - 2] .)) {// 多重复一次和 s 串前移一位的结果一样// 为什么 | 相当于判断两次只要有一次 true 就算 truedp[i][j] | dp[i - 1][j];}}}}}return dp[m][n];}
}二刷
倒没想象中那么恶心了主要还是分好情况然后再考虑如何dp注意状态转移方程用到的最优子结构。
class Solution {public boolean isMatch(String s, String p) {boolean[][] dp new boolean[s.length() 1][p.length() 1];for(int i 0; i s.length(); i) {for(int j 0; j p.length(); j) {if(j 0) {dp[i][j] (i 0);continue;}// Case 1: 没碰到 * 的情况if(p.charAt(j - 1) ! *) {if(i 0 (s.charAt(i - 1) p.charAt(j - 1) || p.charAt(j - 1) .)) {dp[i][j] dp[i - 1][j - 1];}}// Case 2: 碰到 * 的情况else {// Case 2.1不用 * if(j 2) {dp[i][j] dp[i][j - 2];}// Case 2.2用 *if(i 1 j 2 (s.charAt(i - 1) p.charAt(j - 2) || p.charAt(j - 2) .)) {// 重复了一次说明可以套用上一个 i 的结果。dp[i][j] | dp[i - 1][j];}}}}return dp[s.length()][p.length()];}
}
