Leetcode JAVA刷刷站（10）正则表达式匹配

一、题目概述

二、思路方向 

       在Java中，实现一个支持'.'和'*'的正则表达式匹配器，可以通过递归或动态规划（DP）的方法来完成。这里，我将使用动态规划的方法来解决这个问题，因为它更容易理解和实现。

       动态规划的思路是，我们可以创建一个二维的布尔数组dp，其中dp[i][j]表示字符串s的前i个字符和模式p的前j个字符是否匹配。初始化时，dp[0][0]为true（空字符串和空模式匹配），而dp[0][j]（对于所有j > 0）只有在p的前j个字符都是*时才为true，因为*可以匹配零个字符。

       接下来，我们遍历dp数组，填充剩余的条目。对于每个(i, j)，我们考虑以下情况：

1. 如果p[j-1]不是*，那么dp[i][j]为真当且仅当s[i-1] == p[j-1]或p[j-1] == '.'且dp[i-1][j-1]为真。
2. 如果p[j-1]是*，那么有两种可能性：
   • 忽略*和前面的字符，即看dp[i][j-2]。
   • 匹配零个或多个前面的字符，这取决于dp[i-1][j]（如果s[i-1]匹配p[j-2]，则可以通过添加s[i-1]到匹配中）为真。

三、代码实现 

public class Solution {  public boolean isMatch(String s, String p) {  int m = s.length();  int n = p.length();  // 创建一个二维布尔数组dp  boolean[][] dp = new boolean[m + 1][n + 1];  dp[0][0] = true; // 空字符串和空模式匹配  // 初始化dp[0][j]，只有当p全是*时才匹配  for (int j = 1; j <= n; j++) {  if (p.charAt(j - 1) == '*') {  dp[0][j] = dp[0][j - 2];  }  }  // 填充dp数组  for (int i = 1; i <= m; i++) {  for (int j = 1; j <= n; j++) {  if (p.charAt(j - 1) != '*') {  dp[i][j] = (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.') && dp[i - 1][j - 1];  } else {  // 两种情况：匹配0次或多次前面的字符  dp[i][j] = dp[i][j - 2]; // 忽略*和前面的字符  if (s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.') {  dp[i][j] = dp[i][j] || dp[i - 1][j];  }  }  }  }  return dp[m][n];  }  public static void main(String[] args) {  Solution solution = new Solution();  System.out.println(solution.isMatch("aa", "a"));    // false  System.out.println(solution.isMatch("aa", "a*"));   // true  System.out.println(solution.isMatch("ab", ".*"));   // true  System.out.println(solution.isMatch("aab", "c*a*b")); // true  System.out.println(solution.isMatch("mississippi", "mis*is*p*.")); // false  }  
}

执行结果：

 四、小结 

       这个实现通过动态规划解决了正则表达式的匹配问题，时间复杂度为O(mn)，空间复杂度也为O(mn)，其中m和n分别是字符串s和模式p的长度。

 结语 

因为遇见你，我才知道我也能具有美丽的记忆。

所以，无论你怎样对待我，

我都会用心去宽恕你的恨

用心去铭记你的好

！！！