leetcode：10. 正则表达式匹配

题目

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

  • '.' 匹配任意单个字符
  • '*' 匹配零个或多个前面的那一个元素

所谓匹配，是要涵盖 整个 字符串 s 的，而不是部分字符串。

示例：

  1. 输入：s = "aa" p = "a"
  2. 输出：false
  3. 解释："a" 无法匹配 "aa" 整个字符串。
  1. 输入：s = "aa" p = "a*"
  2. 输出：true
  3. 解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
  1. 输入：s = "ab" p = ".*"
  2. 输出：true
  3. 解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。
  1. 输入：s = "aab" p = "c*a*b"
  2. 输出：true
  3. 解释：因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。
  1. 输入：s = "mississippi" p = "mis*is*p*."
  2. 输出：false

解答 & 代码

动态规划：
image.png
[困难] 10. 正则表达式匹配

  1. class Solution {
  2. private:
  3.     bool match(char a, char b)
  4.     {
  5.         return a == b || b == '.';
  6.     }
  7. public:
  8.     bool isMatch(string s, string p) {
  9.         int sLen = s.size();
  10.         int pLen = p.size();
  11.         // 1. 定义 dp 数组
  12.         // dp[i][j] 代表 s 的前 i 个字符 s[0..i-1] 和 p 的前 j 个字符 p[0...j-1] 是否匹配
  13.         vector<vector<bool>> dp(sLen + 1, vector<bool>(pLen + 1, false));
  15.         // 2. 初始化
  16.         // 2.1 若 s 和 p 都是空串，则匹配，即 dp[0][0]=True
  17.         dp[0][0] = true;
  18.         // 2.2 若 p 为空串，s 不为空，则肯定不匹配，因此 dp 数组第一列 dp[i][0] = false
  19.         for(int i = 1; i <= sLen; ++i)
  20.             dp[i][0] = false;
  21.         // 2.3 若 s 为空串，p 不为空，如果要匹配，则必须 p 最右端是 'x*'，匹配 0 次，
  22.         // 因此 dp 数组第一行 dp[0][j] = p[j - 1] == '*' && dp[0][j - 2]
  23.         dp[0][1] = false;    // 若 s 为空串，p 只有一个字符，则肯定不匹配
  24.         for(int j = 2; j <= pLen; ++j)
  25.             dp[0][j] = p[j - 1] == '*' && dp[0][j - 2];
  27.         // 3. 状态转移
  28.         for(int i = 1; i <= sLen; ++i)
  29.         {
  30.             for(int j = 1; j <= pLen; ++j)
  31.             {
  32.                 if(p[j - 1] == '*')
  33.                 {
  34.                     if(match(s[i - 1], p[j - 2]))
  35.                         dp[i][j] = dp[i][j - 2] || dp[i - 1][j - 2] || dp[i - 1][j];
  36.                     else
  37.                         dp[i][j] = dp[i][j - 2];
  38.                 }
  39.                 else
  40.                     dp[i][j] = match(s[i - 1], p[j - 1]) && dp[i - 1][j - 1];
  41.             }
  42.         }
  44.         return dp[sLen][pLen];
  45.     }
  46. };

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

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

执行结果：

  1. 执行结果：通过
  3. 执行用时：4 ms, 在所有 C++ 提交中击败了 85.10% 的用户
  4. 内存消耗：6.7 MB, 在所有 C++ 提交中击败了 71.79% 的用户

相似题目

[困难] 44. 通配符匹配