【Leetcode】10. 正则表达式匹配

10. 正则表达式匹配（困难）

1. 题解

   • 如果从左向右进行匹配的话，需要考虑字符后是否有 * 。

     

   • 因此选择从右向左扫描更为简单。

     *前面肯定有一个字符，它像是一个拷贝器，能够复制前面的单个字符，甚至也可以把这个字符消除（出现 0 次）。

     两个字符串是否匹配，取决于最右边的字符是否匹配，以及剩余的子串是否匹配。其中，「剩余的子串是否匹配」，就是本道题的子问题。

     

   • 状态定义：定义 dp[i][j] 为第一个字符串到 i 为止，第二个字符串到 j 为止，两个字符串是否匹配。如果匹配，dp[i][j] = true；如果不匹配，dp[i][j] = false。

   • 子问题的考虑

     • 情况一：s[i-1] 和 p[j-1] 匹配，即 s[i-1] == p[j-1] || p[j-1] == '.'。那么只需要考虑剩余的子串是否匹配，即 dp[i][j] = dp[i-1][j-1];

       

     • 情况二：s[i-1] 和 p[j-1] 不匹配。这时候不能直接认为两个字符串不匹配，而是需要进一步考虑 p[j-1] == '*' 的情况。但是如果不是 * ，那么肯定不匹配。

       

       对于 * ，它可以匹配 0 个或多个字符。当s[i-1] 和 p[j-2] 匹配，且 p[j-1] == ‘*’ 时，需要考虑三种情况： * 使 dp[j-2] 出现 0 次、1 次或 >=2次。只要其中一种情况能使得两个子串匹配，我们就可以继续考虑剩余子串是否匹配。状态转移方程为：dp[i][j] = dp[i][j-2] || dp[i-1][j-2] || dp[i-1][j];

       
       当s[i-1] 和 p[j-2] 不匹配，且 p[j-1] == ‘*’ 时，可以利用 * 消除不匹配字符 p[j-2]，考虑 s[i-1] 和 p[j-3] 是否匹配。状态转移方程为：dp[i][j] = dp[i][j-2];。

   • 初始情况：当两个字符串都是空串的时候，一定匹配，因此 dp[0][0] = true; ；当 s 为空时，如果 p 的右端字符是 * ，那么就可以使得 p 也变成空串；当 p 为空，两个字符串一定不匹配。

2. 代码

   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;// 如果s为空串 p[j-1]=* 也能够匹配for(int j=1; j<=n; ++j){if(p[j-1] == '*'){dp[0][j] = dp[0][j-2];}}// 从右向左匹配for(int i=1; i<=m; ++i){for(int j=1; j<=n; ++j){// s[i-1]和p[j-1]匹配if(s[i-1] == p[j-1] || p[j-1] == '.'){dp[i][j] = dp[i-1][j-1];}// s[i-1]和p[j-1]不匹配else{// p[j-1] == '*' 且 s[i-1]和p[j-2]匹配if(p[j-1] == '*'){dp[i][j] = dp[i][j-2];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];}}}}}return dp[m][n];}
   };
   

3. 收获

   • 理解错了 * 的意思，* 类似于一个拷贝器 ，能匹配前一个元素，也能消除前一个元素（匹配零个）。
   • 这道题需要考虑多种情况，感觉很难想得这么全面。