题目描述

给定一个字符串 (s) 和一个字符模式 (p)。实现支持 '.' 和 '*' 的正则表达式匹配。

  1. '.' 匹配任意单个字符。
  2. '*' 匹配零个或多个前面的元素。

匹配应该覆盖整个字符串 (s) ，而不是部分字符串。

说明:

  • s 可能为空，且只包含从 a-z 的小写字母。

  • p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。

示例 1:

  1. 输入:
  2. s = "aa"
  3. p = "a"
  4. 输出: false
  5. 解释: "a" 无法匹配 "aa" 整个字符串。

示例 2:

  1. 输入:
  2. s = "aa"
  3. p = "a*"
  4. 输出: true
  5. 解释: '*' 代表可匹配零个或多个前面的元素, 即可以匹配 'a' 。因此, 重复 'a' 一次, 字符串可变为 "aa"。

示例 3:

  1. 输入:
  2. s = "ab"
  3. p = ".*"
  4. 输出: true
  5. 解释: ".*" 表示可匹配零个或多个('*')任意字符('.')。

示例 4:

  1. 输入:
  2. s = "aab"
  3. p = "c*a*b"
  4. 输出: true
  5. 解释: 'c' 可以不被重复, 'a' 可以被重复一次。因此可以匹配字符串 "aab"。

示例 5:

  1. 输入:
  2. s = "mississippi"
  3. p = "mis*is*p*."
  4. 输出: false

题解

DP

参考：Java DP solution beats %100 with explanation 👍

用 dp[i,j] 表示 s.Substring(0,i) 是否可以用 p.Substring(0,j) 匹配。例如 dp[0,0] = true，因为当 s 和 p 都是空时它们相匹配。

  1. s='aab', p='c*a*b'
  3.       c * a * b 
  4.     0 1 2 3 4 5
  5.   0 y
  6. a 1
  7. a 2
  8. b 3

针对第一列 p = “” 只有字符串 s = “” 与它匹配，那就是 dp[0,0]，这也意味着第一列除了 dp[0,0] 都是 false。

  1. s='aab', p='c*a*b'
  3.       c * a * b 
  4.     0 1 2 3 4 5
  5.   0 y
  6. a 1 n
  7. a 2 n
  8. b 3 n

针对第一行 s = “”，p = “” 或 p =”a“(任意字符) 都能与它匹配，甚至 p = “abc*” 都能与其匹配。下面就是循环填充第一行的代码：

  1. for (int j=2; j<=p.length(); j++) 
  2. {
  3.     dp[0][j] = p.charAt(j-1) == '*' && dp[0][j-2]; 
  4. }

处理完第一行和第一列后我们的矩阵就变成了：
注意因为 p = “c“ 和 p=”ca*” 都能匹配空字符串，所以 dp[0,2] 和 dp[0,4] 是 true。

  1. s='aab', p='c*a*b'
  3.       c * a * b 
  4.     0 1 2 3 4 5
  5.   0 y n y n y n
  6. a 1 n
  7. a 2 n
  8. b 3 n

现在我们可以开始主循环了。分两种情况：

  1. p[j-1] == s[i-1] || p[j-1] == '.' ：如果当前字符相同或表达式是 . 那匹配与否由之前的状态决定 dp[i,j] = dp[i-1,j-1]。之所以索引都是 i-1,j-1 有 -1 的偏移，是因为我们的 dp 数组尺寸比字符串大 1，以保存初始状态 dp[0,0]

  2. 如果 p[j-1] == '*' 那么可以将它视为一个空集， dp[i,j] 等于 dp[i,j-2] 或 (s[i-1] p[j-2] || p[j-2] == '.') 。又因为当前的字符需要与表达式 * 之前的字符相匹配，所以还需要与 dp[i-1,j]

于是最终的 dp 矩阵如下：

  1. s='aab', p='c*a*b'
  3.       c * a * b 
  4.     0 1 2 3 4 5
  5.   0 y n y n y n
  6. a 1 n n n y y n
  7. a 2 n n n n y n
  8. b 3 n n n n n y

DP 代码：

  1. public bool IsMatch(string s, string p)
  2. {
  3.     if (string.IsNullOrEmpty(p)) return string.IsNullOrEmpty(s);
  5.     var dp = new bool[s.Length + 1, p.Length + 1];
  6.     dp[0, 0] = true;
  8.     for (var j = 2; j <= p.Length; j++)
  9.     {
  10.         dp[0, j] = p[j - 1] == '*' && dp[0, j - 2];
  11.     }
  13.     for (var j = 1; j <= p.Length; j++)
  14.     {
  15.         for (var i = 1; i <= s.Length; i++)
  16.         {
  17.             if (p[j - 1] == s[i - 1] || p[j - 1] == '.')
  18.             {
  19.                 dp[i, j] = dp[i - 1, j - 1];
  20.             }
  21.             else if (p[j - 1] == '*')
  22.             {
  23.                 dp[i, j] = dp[i, j - 2] || ((s[i - 1] == p[j - 2] || p[j - 2] == '.') && dp[i - 1, j]);
  24.             }
  25.         }
  26.     }
  27.     return dp[s.Length, p.Length];
  28. }

时间和空间复杂度都是 O(p.Length * s.Length)。