#include "s0010_regular_expression_matching.hpp"

// 动态规划
// 当前匹配成功 == 之前匹配成功 && 当前字符匹配成功

bool S0010::isMatch(string s, string p) {
  int m = s.size();
  int n = p.size();

  auto matches = [&](int i, int j) {
    if (i == 0) {
      return false;
    }
    if (p[j - 1] == '.') {
      return true;
    }
    return s[i - 1] == p[j - 1];
  };

  vector<vector<int>> f(m + 1, vector<int>(n + 1));
  f[0][0] = true;
  for (int i = 0; i <= m; ++i) {
    for (int j = 1; j <= n; ++j) {
      if (p[j - 1] == '*') {
        f[i][j] |= f[i][j - 2];
        if (matches(i, j - 1)) {
          f[i][j] |= f[i - 1][j];
        }
      } else {
        if (matches(i, j)) {
          f[i][j] |= f[i - 1][j - 1];
        }
      }
    }
  }
  return f[m][n];
}