C++ standard DP without tricks, not so fast but accepted

• ``````Define a function L(j, i) to represent if there is a match between  s[j], s[j+1] ... s[m + 1] and p[i], p[i+1], ... ,p[n + 1]
Boundary:
L(m + 1, n + 1) = 1   (empty matches empty)
L(m + 1, i) = 1 (if i start from n , and characters between p[i]...p[n] are all '*')
Recurrence:
{for k = j to m + 1, if there exist a L(k, i + 1)  == true then true, otherwise false}  (if p[i] == '*')
L(j, i) =      L(j + 1, i + 1) (if p[i] == '?')
{L(j + 1, i + 1) if s[j] == p[i], false otherwise} (if p[i] == other characters)
``````

//Code:

``````class Solution {
public:

bool isMatch(string s, string p) {
int m = s.length(), n = p.length();
if(n == 0 && m != 0) return false;
vector<char> dp_row(s.length() + 1, 0);
vector<vector<char>> dp_arr(p.length() + 1, dp_row);

dp_arr[n][m] = 1;
for(int i = n-1; i >= 0; i--){
if(p[i] == '*') dp_arr[i][m] = 1;
else break;
}
for(int i = n - 1; i >= 0; i--){
for(int j = m - 1; j >= 0; j--){
if(p[i] == '*'){
bool found_valid = false;
for(int k = j; k <= m; k++){
if(dp_arr[i+1][k] == 1){
found_valid = true;
break;
}
}
if(found_valid) dp_arr[i][j] = 1;
else dp_arr[i][j] = 0;
} else if(p[i] == '?'){
dp_arr[i][j] = dp_arr[i+1][j+1];
} else {
if(p[i] == s[j]) dp_arr[i][j] = dp_arr[i+1][j+1];
else dp_arr[i][j] = 0;
}
}
}
if(dp_arr[0][0]== 1) return true;
else return false;
}

};``````

• Thanks to your idea,I came up with the following code.But the result is always TLE and I still cannot find why it happens.Could you please help me find what's wrong with my code?

``````bool isMatch(string s, string p)
{
int m = s.length(), n = p.length();
if(n==0&&m!=0){return false;}
vector<vector<bool>>dp(m+1, vector<bool>(n+1,false));
dp[0][0] = true;
for (int i = 1; i <= m; i++)
{
dp[i][0] = false;
}
for (int j = 1; j <= n;j++)
{
if (p[j - 1] == '*') { dp[0][j] = true; }
else { break; }
}
for (int i = 1; i <= m; i++)
{
for (int j = 1; j <= n; j++)
{
if (p[j - 1] == '*') {
dp[i][j] = false;
for (int k = 0; k <= i; k++) {
if (dp[k][j - 1] ) { dp[i][j] = true; break; }
}
//if (dp[i - 1][j]) { dp[i][j] = true; }
}
else if (p[j - 1] == '?') {
dp[i][j] = dp[i - 1][j - 1];
}
else {
if (s[i-1] == p[j-1]) { dp[i][j] = dp[i - 1][j - 1]; }
else { dp[i][j] = false; }
}
}
}
return dp[m][n];
}``````

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