leetcode 链接：正则表达式匹配

题目

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖整个字符串 s 的，而不是部分字符串。

示例：

输入：s = "aa" p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。

输入：s = "aa" p = "a*"
输出：true
解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。

输入：s = "ab" p = ".*"
输出：true
解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。

输入：s = "aab" p = "c*a*b"
输出：true
解释：因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。

输入：s = "mississippi" p = "mis*is*p*."
输出：false

解答 & 代码

参考：「手画图解」动态规划，需要仔细的分情况讨论

动态规划：

定义数组：设置二维数组 **dp**，dp[i][j] 代表字符串 s 的前 i 个字符 s(0,...,i-1) 和字符规律 p 的前 j 个字符 p(0,...,j-1) 是否匹配
状态转移方程：dp[i][j] = ?
- 如果字符规律 p 的最右端字符 p[j - 1] 不是 '*'：那么只有当同时满足以下两个条件时，dp[i][j] = True
  - 字符规律 p 的最右端字符 p[j - 1] 和字符串 s 的最右端字符 s[i - 1] 匹配，即满足以下任意一种情况：
    - p[j - 1] == '.'
    - p[j - 1] == s[i - 1]
  - dp[i - 1][j - 1] == True，即 p 和 s 都去掉最右端字符后，剩余子串匹配
- 如果字符规律 p 的最右端字符 p[j - 1] 是 '*'，分为两种情况：
  - 如果 p 中 '*' 之前的字符 p[j - 2] 和 s 的最右端字符 s[i - 1] 匹配，则有以下几种情况：
    - 若 '*' 让字符 p[j - 2] 匹配 0 次，那么 dp[i][j] = dp[i][j - 2]，即考察子串 s(0,...,i-1) 和 p(0,...,j-3) 是否匹配（即 s 不变，抵消掉 p 右边末尾的 'x*'）
    - 若 '*' 让字符 p[j - 2] 匹配 1 次，那么 dp[i][j] = dp[i - 1][j - 2]，即考察子串 s(0,...,i-2) 和 p(0,...,j-3) 是否匹配（即 s 最右端字符和 p 右边末尾的 'x*' 抵消）
    - 若 '*' 让字符 p[j - 2] 匹配 2 次及以上，那么 dp[i][j] = dp[i - 1][j]，即考察子串 s(0,...,i-2) 和 p(0,...,j-1) 是否匹配（即 s 最右端字符被抵消，而 p 右边末尾的 'x*' 保留，继续往左匹配子串 s(0,...,i-2) 和 p(0,...,j-1) ）
  - 如果 p 中 '*' 之前的字符 p[j - 2] 和 s 的最右端字符 s[i - 1] 不匹配，那么就相当于 p 右边末尾的 'x*' 匹配 0 次，被抵消掉，而 s 不变，继续往左匹配子串 s(0,...,i-1) 和 p(0,...,j-3) ，因此， dp[i][j] = dp[i][j - 2]

初始化：

若 s 和 p 都为空串，则匹配，即 dp[0][0]=True
若 p 为空串，s 不为空，则肯定不匹配，因此 dp 数组第一列 dp[i][0] = false

若 s 为空串，p 不为空，如果要匹配，则必须 p 最右端是 'x*'，匹配 0 次，因此 dp 数组第一行 dp[0][j] = dp[0][j - 2]

class Solution {
private:
bool matches(char a, char b)
{
   return b == '.' || a == b;
}
public:
bool isMatch(string s, string p) {
   int lenS = s.size();
   int lenP = p.size();        
   // 1. 定义 dp 数组
   vector<vector<bool>> dp(lenS + 1, vector<bool>(lenP + 1, false));
   // 2. 初始化
   // 2.1 若 s 和 p 都为空串，则匹配
   dp[0][0] = true;
   // 2.2 若 p 为空串，s 不为空，则肯定不匹配，因此 dp 数组第一列 dp[i][0] = false，在定义数组时已经将所有元素默认初始化为 false
   // 2.3 若 s 为空串，p 不为空，如果要匹配，则必须 p 最右端是 'x*'，匹配 0 次，因此 dp 数组第一行 dp[0][j] = dp[0][j - 2]
   for(int j = 1; j <= lenP; ++j)
   {
       if(p[j - 1] == '*')
           dp[0][j] = dp[0][j - 2];
   }

   // 3. 状态转移
   for(int i = 1; i <= lenS; ++i)
   {
       for(int j = 1; j <= lenP; ++j)
       {
           // 如果 p 最右端为 '*'
           if(p[j - 1] == '*')
           {
               if(matches(s[i - 1], 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];
           }
           // p 最右端不是 '*'
           else
           {
               dp[i][j] = matches(s[i - 1], p[j - 1]) && dp[i - 1][j - 1];
           }
       }
   }
   return dp[lenS][lenP];
}
};

复杂度分析：设字符串 s、p 长度分别为 M、N

时间复杂度 O(MN)
空间复杂度 O(MN)：二维 dp 数组

执行结果：

执行结果：通过

执行用时：4 ms, 在所有 C++ 提交中击败了 90.02% 的用户
内存消耗：6.9 MB, 在所有 C++ 提交中击败了 53.63% 的用户

CodeTop 企业题库

[困难] 10. 正则表达式匹配

题目

解答 & 代码