//

// Solution44.cpp

// Algorithm

//

// Created by Pancf on 2020/10/25.

// Copyright © 2020 Pancf. All rights reserved.

//

#include "Solution44.hpp"

#include <vector>

bool Solution44::isMatch(std::string s, std::string p)

{

int row = (int)s.size(), col = (int)p.size();

// matrix[i][j] means whether p[0, j-1] matches s[0, i-1] or not

std::vector<std::vector<bool>> matrix(row + 1, std::vector<bool>(col + 1, false));

matrix[0][0] = true;

for (int i = 1; i <= col; ++i) {

if (p[i - 1] == '*') matrix[0][i] = true;

else break;

}

for (int i = 1; i <= row; ++i) {

for (int j = 1; j <= col; ++j) {

// whether p[0, j-1] matches s[0, i-1]

if (p[j - 1] != '*') {

// p[j-1] match? s[i-1]

matrix[i][j] = (p[j - 1] == '?' || p[j - 1] == s[i - 1]) && matrix[i - 1][j - 1];

} else {

// '*' matches nothing(matrix[i][j-1]) or one character(matrix[i-1][j])

matrix[i][j] = matrix[i][j - 1] || matrix[i - 1][j];

}

}

}

return matrix[row][col];

// int i = 0, j = 0, match = 0, starIdx = -1;

// while (i < s.size()){

// // s[i] p[j]匹配，索引各自后移1位

// if (j < p.size() && (p[j] == '?' || s[i] == p[j])) {

// i++;

// j++;

// } else if (j < p.size() && p[j] == '*') {

// // p[j] == '*'，记录*的位置以便回溯

// starIdx = j++;

// match = i;

// } else if (starIdx != -1) {

// // 回溯时将*上次对应匹配的索引match自增，然后赋值给匹配串索引

// j = starIdx + 1;

// i = ++match;

// } else return false;

// }

// while (j < p.size() && p[j] == '*')

// j++;

//

// return j == p.size();

}