一、题目内容

image.png

二、题解

解法1：

思路

image.png

代码

  1. class Solution {
  2.     public boolean isMatch(String s, String p) {
  3.         s = '0' + s;
  4.         p = '0' + p;
  5.         int m = s.length(), n = p.length();
  6.         boolean[][] dp = new boolean[m][n];
  7.         dp[0][0] = true;
  9.         // 初始化首行
  10.         for (int j = 2; j < n; j += 2) {
  11.             dp[0][j] = dp[0][j - 2] && p.charAt(j) == '*';
  12.         }
  13.         // 状态转移
  14.         for (int i = 1; i < m; i++) {
  15.             for (int j = 1; j < n; j++) {
  16.                 if (p.charAt(j) == '*') {
  17.                     if (dp[i][j - 2]) {// *销毁前面的字符，出现0次
  18.                         dp[i][j] = true;
  19.                     } else if (dp[i - 1][j] && p.charAt(j - 1) == s.charAt(i)) {
  20.                         dp[i][j] = true;
  21.                     } else if (dp[i - 1][j] && p.charAt(j - 1) == '.') {
  22.                         dp[i][j] = true;
  23.                     }
  24.                 } else {
  25.                     if (dp[i - 1][j - 1] && s.charAt(i) == p.charAt(j)) {
  26.                         dp[i][j] = true;
  27.                     } else if (dp[i - 1][j - 1] && p.charAt(j) == '.') {
  28.                         dp[i][j] = true;
  29.                     }
  30.                 }
  31.             }
  32.         }
  33.         return dp[m - 1][n - 1];
  34.     }
  35. }