题目描述

原题链接

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

‘.’ 匹配任意单个字符
‘*’ 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。


示例 1：

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

示例 2:

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

示例 3：

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

提示：

  • 1 <= s.length <= 20
  • 1 <= p.length <= 30
  • s 只包含从 a-z 的小写字母。
  • p 只包含从 a-z 的小写字母，以及字符 . 和 *。
  • 保证每次出现字符 * 时，前面都匹配到有效的字符

    个人解法

Java（递归）

  1. public static boolean isMatch(String s, String p) {
  2.         int pl=p.length(),sl=s.length();
  3.         //如果p长为0，s不为0肯定无法匹配（s=“a”，p=“”）
  4.         if (pl == 0) {
  5.             return sl == 0;
  6.         }
  7.         //存储判断第一个字符是否可能相等的结果
  8.         //①s="a",p="a" ②s="a",p="." 这两种情况都相等
  9.         boolean result = (sl != 0 && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.'));
  10.         if (pl>=2&&p.charAt(1)=='*') {
  11.             //s="aaabc",p="a*abc"
  12.             //左=>新s="aaabc",新p="abc“假设a*代表0个字符
  13.             //右=>新s="aabc",新p="a*abc"假设从s中取出一个a(可能和p中不一样，那就是false)消掉
  14.             return isMatch(s,p.substring(2))||(result&&isMatch(s.substring(1),p));
  15.         }else {
  16.             //s[0]=p[0]&&sl=1&&pl=1 s="a",p="a"
  17.             //s[0]=p[0]&&p[1]!="*" s="ab",p="ab*"相当于判断s="b",p="b*"
  18.             //s[0]!=p[0]&&p[1]!="*" s="ab",p="bb*" 结果为false
  19.             return result&&isMatch(s.substring(1),p.substring(1));
  20.         }
  21.     }

JavaScript

  1. /**
  2.  * @param {string} s
  3.  * @param {string} p
  4.  * @return {boolean}
  5.  */
  6. var isMatch = function (s, p) {
  7.   if (p.length === 0) {
  8.     return s.length === 0;
  9.   }
  10.   const result = s.length !== 0 && (s[0] === p[0] || p[0] === '.');
  11.   if (p.length >= 2 && p[1] === '*') {
  12.     return isMatch(s, p.substring(2)) || (result && isMatch(s.substring(1), p));
  13.   } else {
  14.     return result && isMatch(s.substring(1), p.substring(1));
  15.   }
  16. };

更优解法

Java（动态规划）

image.png
消掉一个a的情况可分解为消掉多个a的第一步以及剩下去消掉0个

  1. class Solution {
  2.     public boolean isMatch(String s, String p) {
  3.         int m = s.length();
  4.         int n = p.length();
  6.         boolean[][] f = new boolean[m + 1][n + 1];
  7.         f[0][0] = true;
  8.         for (int i = 0; i <= m; ++i) {
  9.             for (int j = 1; j <= n; ++j) {
  10.                 //如果p(j-1)等于"*"
  11.                 if (p.charAt(j - 1) == '*') {
  12.                     //s消掉0个相同字符
  13.                     f[i][j] = f[i][j - 2];
  14.                     //s消掉一个相同字符或其他情况
  15.                     if (matches(s, p, i, j - 1)) {
  16.                         f[i][j] = f[i][j] || f[i - 1][j];
  17.                     }
  18.                 } else {
  19.                     //如果p(j-1)≠"*"
  20.                     if (matches(s, p, i, j)) {
  21.                         f[i][j] = f[i - 1][j - 1];
  22.                     }
  23.                 }
  24.             }
  25.         }
  26.         return f[m][n];
  27.     }
  29.     public boolean matches(String s, String p, int i, int j) {
  30.         if (i == 0) {
  31.             return false;
  32.         }
  33.         if (p.charAt(j - 1) == '.') {
  34.             return true;
  35.         }
  36.         return s.charAt(i - 1) == p.charAt(j - 1);
  37.     }
  38. }

JavaScript

  1. let isMatch = function (s, p) {
  2.     let dp = Array(s.length + 1);
  3.     for (let i = 0; i < dp.length; i++) {
  4.         dp[i] = Array(p.length + 1).fill(false)
  5.     }
  6.     dp[0][0] = true;
  7.     for (let i = 1; i < p.length; i++) {
  8.         if (p.charAt(i) === "*") {
  9.             dp[0][i + 1] = dp[0][i - 1]
  10.         }
  11.     }
  13.     for (let i = 0; i < s.length; i++) {
  14.         for (let j = 0; j < p.length; j++) {
  15.             if (p.charAt(j) === '.') {
  16.                 dp[i + 1][j + 1] = dp[i][j]
  17.             }
  19.             if (p.charAt(j) === s.charAt(i)) {
  20.                 dp[i + 1][j + 1] = dp[i][j]
  21.             }
  23.             if (p.charAt(j) === '*') {
  24.                 if (p.charAt(j - 1) !== s.charAt(i) && p.charAt(j - 1) !== '.') {
  25.                     dp[i + 1][j + 1] = dp[i + 1][j - 1]
  26.                 } else {
  27.                     dp[i + 1][j + 1] = (dp[i + 1][j] || dp[i][j + 1] || dp[i + 1][j - 1])
  28.                 }
  29.             }
  30.         }
  31.     }
  32.     return dp[s.length][p.length]
  33. };