LeetCode-10 正則表達式匹配

動態規劃

10. 正則表達式匹配

dp數組含義：$dp[i][j]$ 表示 $s[0:i?1]$ 能否被 $p[0:j?1]$ 成功匹配。

狀態轉移方程 ：

• 如果 $s[i?1]==p[j?1]$ ，那么當前字符是匹配成功了，整個子串是否匹配成功取決于之前的子串能否匹配，即 $dp[i][j]=d[i?1][j?1]$ 。
• 如果 $s[i?1]=p[j?1]$ ，可以按 $p[j?1]$ 是什么分三種情況：
  • 如果 $p[j?1]$ 是 . 或 * 之外的字符，那肯定不匹配了，$dp[i][j]=false$
  • 如果 $p[j?1]={=}^{\prime }{.}^{\prime }$ ，由于 . 可以匹配任何字符，因此當前字符也肯定匹配成功了，還是取決于之前的子串，即 $dp[i][j]=dp[i?1][j?1]$ 。
  • 如果 $p[j?1]={=}^{\prime }{?}^{\prime }$ ，情況比較復雜，需要再看 $p[j?2]$ 與 $s[i?1]$ 的關系，因為 $p[j?2]$ 要與 $s[i?1]$ 匹配上，$p[j?1]$ 的這個 * 才有用
    • 而所謂 ”匹配上“，可能有兩種情況，一個是字符相同，即 $p[j?2]=s[i?1]$；另一個是 $p[j?2]$ 是 . ，匹配任意字符。可以再按照 $p[j?1]$ 這個 * 讓 $s[i?1]$ 這個字符出現幾次來分，零次、一次或兩次及以上：
      • $p[j?1]$ 匹配零個 $s$ 中字符，相當于刪掉 * 自己及其之前的一個字符，看能不能匹配成功，比如 ### 和 ###a* ，這時 $dp[i][j]=dp[i][j?2]$ ；
      • $p[j?1]$ 匹配一個 $s$ 中字符，相當于把 * 自己刪掉，看能不能匹配成功，比如 ### 和 ###*，這時 $dp[i][j]=dp[i?1][j?2]$ ；
      • $p[j?1]$ 匹配多個 $s$ 中字符，這時 $dp[i][j]=dp[i?1][j]$
      • 注意，以上三種情況只要滿足一種即可，是 或 的關系。
    • 如果未能匹配上，即 $p[j-2]\ne s[i-1] $ 且 $p[j?2]{=}^{\prime }{.}^{\prime }$ ，這時 $p[j?1]$ 的這個 * 可以把沒能匹配上的 $p[j?2]$ 刪掉，因此就取決于再之前的子串是否匹配：$dp[i][j]=dp[i][j?2]$ 。

初始化

首先 $dp[0][0]$ 即 $s$ 和 $p$ 均為空時， 認為是可以匹配的，之后的 $dp[0][j]$ 要先看 $p[j?1]$ 是否為 * ，若為 * ，則 $dp[0][j]=dp[0][j?2]$ 。

其他位置均初始化為 $false$ 。

遍歷順序

從前到后即可

class Solution {
public:bool isMatch(string s, string p) {int m = s.size(), n = p.size();vector<vector<bool>> dp(m+1, vector<bool> (n+1, false));dp[0][0] = true;for (int j=1; j<n+1; ++j) {if (p[j-1] == '*') dp[0][j] = dp[0][j-2];}for (int i=1; i<m+1; ++i) {for (int j=1; j<n+1; ++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/