黄石做网站的,微网站建设的三个步骤,便宜网站建设成都,传奇网络游戏LeetCode-10 正则表达式匹配
动态规划
10. 正则表达式匹配
dp数组含义#xff1a;dp[i][j]dp[i][j]dp[i][j] 表示 s[0:i−1]s[0:i-1]s[0:i−1] 能否被 p[0:j−1]p[0:j-1]p[0:j−1] 成功匹配。
状态转移方程 #xff1a;
如果 s[i−1]p[j−1]s[i-1]p[j-1]s[i−1]p[j−1] …LeetCode-10 正则表达式匹配
动态规划
10. 正则表达式匹配
dp数组含义dp[i][j]dp[i][j]dp[i][j] 表示 s[0:i−1]s[0:i-1]s[0:i−1] 能否被 p[0:j−1]p[0:j-1]p[0:j−1] 成功匹配。
状态转移方程
如果 s[i−1]p[j−1]s[i-1]p[j-1]s[i−1]p[j−1] 那么当前字符是匹配成功了整个子串是否匹配成功取决于之前的子串能否匹配即 dp[i][j]d[i−1][j−1]dp[i][j]d[i-1][j-1]dp[i][j]d[i−1][j−1] 。如果 s[i−1]≠p[j−1]s[i-1]\ne p[j-1]s[i−1]p[j−1] 可以按 p[j−1]p[j-1]p[j−1] 是什么分三种情况 如果 p[j−1]p[j-1]p[j−1] 是 . 或 * 之外的字符那肯定不匹配了dp[i][j]falsedp[i][j]falsedp[i][j]false如果 p[j−1]′.′p[j-1].p[j−1]′.′ 由于 . 可以匹配任何字符因此当前字符也肯定匹配成功了还是取决于之前的子串即 dp[i][j]dp[i−1][j−1]dp[i][j]dp[i-1][j-1]dp[i][j]dp[i−1][j−1] 。如果 p[j−1]′∗′p[j-1]*p[j−1]′∗′ 情况比较复杂需要再看 p[j−2]p[j-2]p[j−2] 与 s[i−1]s[i-1]s[i−1] 的关系因为 p[j−2]p[j-2]p[j−2] 要与 s[i−1]s[i-1]s[i−1] 匹配上p[j−1]p[j-1]p[j−1] 的这个 * 才有用 而所谓 ”匹配上“可能有两种情况一个是字符相同即 p[j−2]s[i−1]p[j-2]s[i-1]p[j−2]s[i−1]另一个是 p[j−2]p[j-2]p[j−2] 是 . 匹配任意字符。可以再按照 p[j−1]p[j-1]p[j−1] 这个 * 让 s[i−1]s[i-1]s[i−1] 这个字符出现几次来分零次、一次或两次及以上 p[j−1]p[j-1]p[j−1] 匹配零个 sss 中字符相当于删掉 * 自己及其之前的一个字符看能不能匹配成功比如 ### 和 ###a* 这时 dp[i][j]dp[i][j−2]dp[i][j]dp[i][j-2]dp[i][j]dp[i][j−2] p[j−1]p[j-1]p[j−1] 匹配一个 sss 中字符相当于把 * 自己删掉看能不能匹配成功比如 ### 和 ###*这时 dp[i][j]dp[i−1][j−2]dp[i][j]dp[i-1][j-2]dp[i][j]dp[i−1][j−2] p[j−1]p[j-1]p[j−1] 匹配多个 sss 中字符这时 dp[i][j]dp[i−1][j]dp[i][j]dp[i-1][j]dp[i][j]dp[i−1][j]注意以上三种情况只要满足一种即可是 或 的关系。 如果未能匹配上即 $p[j-2]\ne s[i-1] $ 且 p[j−2]≠′.′p[j-2]\ne .p[j−2]′.′ 这时 p[j−1]p[j-1]p[j−1] 的这个 * 可以把没能匹配上的 p[j−2]p[j-2]p[j−2] 删掉因此就取决于再之前的子串是否匹配dp[i][j]dp[i][j−2]dp[i][j]dp[i][j-2]dp[i][j]dp[i][j−2] 。
初始化
首先 dp[0][0]dp[0][0]dp[0][0] 即 sss 和 ppp 均为空时 认为是可以匹配的之后的 dp[0][j]dp[0][j]dp[0][j] 要先看 p[j−1]p[j-1]p[j−1] 是否为 * 若为 * 则 dp[0][j]dp[0][j−2]dp[0][j]dp[0][j-2]dp[0][j]dp[0][j−2] 。
其他位置均初始化为 falsefalsefalse 。
遍历顺序
从前到后即可
class Solution {
public:bool isMatch(string s, string p) {int m s.size(), n p.size();vectorvectorbool dp(m1, vectorbool (n1, false));dp[0][0] true;for (int j1; jn1; j) {if (p[j-1] *) dp[0][j] dp[0][j-2];}for (int i1; im1; i) {for (int j1; jn1; j) {if (s[i-1] p[j-1] || p[j-1] .) dp[i][j] dp[i-1][j-1];else if (p[j-1] *) {if (s[i-1] p[j-2] || p[j-2] .) {dp[i][j] dp[i][j-2] || dp[i-1][j-2] || dp[i-1][j];}else {dp[i][j] dp[i][j-2];}}}}return dp[m][n];}
};Ref
https://leetcode.cn/problems/regular-expression-matching/solution/shou-hui-tu-jie-wo-tai-nan-liao-by-hyj8/
https://leetcode.cn/problems/regular-expression-matching/solution/dong-tai-gui-hua-zen-yao-cong-0kai-shi-si-kao-da-b/
