//
// 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"));
}