//
// Created by andrew on 2024年9月28日.
//

#include <string>
#include <vector>
#include <unordered_set>

#include <iostream>
#include <gtest/gtest.h>
#include <climits>

using namespace std;

class Solution {
public:
 bool isMatch(const std::string& s, const std::string& p) {
 int m = s.length(), n = p.length();
 std::vector<std::vector<bool>> dp(m + 1, std::vector<bool>(n + 1, false));
 dp[0][0] = true;

 for (int j = 2; j <= n; ++j) {
 dp[0][j] = dp[0][j - 2] && p[j - 1] == '*';
 }

 for (int i = 1; i <= m; ++i) {
 for (int j = 1; j <= n; ++j) {
 if (p[j - 1] == '.' || s[i - 1] == p[j - 1]) {
 dp[i][j] = dp[i - 1][j - 1];
 } else if (p[j - 1] == '*') {
 dp[i][j] = dp[i][j - 2] || (dp[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.'));
 }
 }
 }
 return dp[m][n];
 }
};


TEST(leetcode9, leetcode) {
 Solution solution;

 EXPECT_EQ(true, solution.isMatch("234", "234"));
}