# My C++ DP solution using one-dimensional array

• ``````class Solution {
public:
bool isMatch(string s, string p) {
if (s.length() == 0 && p.length() == 0) return true;
bool dp[p.length()];
bool placeHolder = true;
// init the dp value when the s is empty
for (int i = 0; i < p.length(); i ++) {
if (p[i] == '*') dp[i] = placeHolder;
else dp[i] = false, placeHolder = false;
}

for (int i = 0; i < s.length(); i ++) {
// first calculate the dp value reversely
for (int j = p.length() - 1; j > 0; j --) {
if (p[j] == '*') dp[j] = dp[j - 1] || dp[j];
else if (p[j] == '?') dp[j] = dp[j - 1];
else dp[j] = dp[j - 1] && s[i] == p[j];
}
if (i == 0) dp[0] = p[0] == s[0] || p[0] == '?' || p[0] == '*';
else if (p[0] != '*') dp[0] = false;
else dp[0] = true;
// add the value missed when using reverse calculation
for (int j = 1; j < p.length(); j ++) {
if (p[j] == '*') dp[j] = dp[j - 1] || dp[j];
}
}

return dp[p.length() - 1];
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.