//
//  Solution10.cpp
//  Algorithm
//
//  Created by Pancf on 2019/12/10.
//  Copyright © 2019 Pancf. All rights reserved.
//

#include "Solution10.hpp"
#include <vector>

using std::vector;

// 递归解法
//bool Solution10::isMatch(string s, string p) {
//    if (p.empty()) {
//        return s.empty();
//    }
//    if (p[1] == '*') {
//        //isMatch(s, p.substr(2)) means x* match empty
//        return isMatch(s, p.substr(2)) || (!s.empty() && (s[0] == p[0] || '.' == p[0]) && isMatch(s.substr(1), p));
//    } else {
//        return !s.empty() && (s[0] == p[0] || '.' == p[0]) && isMatch(s.substr(1), p.substr(1));
//    }
//}
// DP解法
bool Solution10::isMatch(string s, string p) {
    //dp[i][j] = true if s[0...i-1] match p[0...j-1], 求dp[s.size()][p.size()]
    //if p[j-1] == '*', dp[i][j] = dp[i][j-2] || ((p[j-2] == s[i-1] || p[j-2] == '.') && dp[i-1][j]),前者是x* match empty,后者是x*匹配xx*
    //else dp[i][j] = dp[i-1][j-1] && ((p[j-1] == s[i-1] || p[j-1] == '.')) && i > 0
    int m = (int)s.size(), n = (int)p.size();
    auto dp = vector<vector<bool>>(m + 1, vector<bool>(n + 1, false));
    dp[0][0] = true;
    for (int i = 0; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (p[j-1] == '*') {
                //p[0] == '*' make no sense
                dp[i][j] = (j >= 2) && (dp[i][j-2] || ((i > 0) && (p[j-2] == s[i-1] || p[j-2] == '.') && dp[i-1][j-1]));
            } else {
                dp[i][j] = (i > 0) && dp[i-1][j-1] && (p[j-1] == s[i-1] || p[j-1] == '.');
            }
        }
    }
    return dp[m][n];
}