# Accepted C++ DP Solution with a Trick

• Updated: Since the OJ has relaxed the time constraint, the following DP solution is now accepted without the trick :-)

Well, so many people has tried to solve this problem using DP. And almost all of them get TLE (if you see a C++ DP solution that gets accepted, please let me know ^_^). Well, this post aims at providing an accpted DP solution which uses a trick to get around the largest test case, insteaed of a solution that is fully correct. So please do not give me down votes for that :-)

Let's briefly summarize the idea of DP. We define the state P[i][j] to be whether s[0..i) matches p[0..j). The state equations are as follows:

1. P[i][j] = P[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '?'), if p[j - 1] != '*';
2. P[i][j] = P[i][j - 1] || P[i - 1][j], if p[j - 1] == '*'.

If you feel confused with the second equation, you may refer to this link. There is an explanation in the comments.

We optimize the DP code to O(m) space by recording P[i - 1][j - 1] using a single variable pre.

The trick to avoid TLE is to hard-code the result for the largest test case by

if (n > 30000) return false;

The complete code is as follows.

class Solution {
public:
bool isMatch(string s, string p) {
int m = s.length(), n = p.length();
if (n > 30000) return false; // the trick
vector<bool> cur(m + 1, false);
cur[0] = true;
for (int j = 1; j <= n; j++) {
bool pre = cur[0]; // use the value before update
cur[0] = cur[0] && p[j - 1] == '*';
for (int i = 1; i <= m; i++) {
bool temp = cur[i]; // record the value before update
if (p[j - 1] != '*')
cur[i] = pre && (s[i - 1] == p[j - 1] || p[j - 1] == '?');
else cur[i] = cur[i - 1] || cur[i];
pre = temp;
}
}
return cur[m];
}
};

For those interested in a fully correct solution, this link has a nice Greedy solution. And I have rewritten the code below to fit the new C++ interface (changed from char* to string).

class Solution {
public:
bool isMatch(string s, string p) {
int m = s.length(), n = p.length();
int i = 0, j = 0, asterisk = -1, match;
while (i < m) {
if (j < n && p[j] == '*') {
match = i;
asterisk = j++;
}
else if (j < n && (s[i] == p[j] || p[j] == '?')) {
i++;
j++;
}
else if (asterisk >= 0) {
i = ++match;
j = asterisk + 1;
}
else return false;
}
while (j < n && p[j] == '*') j++;
return j == n;
}
};

• haha, this is a good solution.
the test case writer is a hentai.
Give me five!!

• if you see a DP solution that gets accepted, please let me know ^_^

Four out of the five top-voted solutions use DP, no?

• Hi, StefanPochmann. I am not clear enough in this sentence. In fact, I want a C++ DP solution. Four of the five top-voted solutions actually use DP, but three of them are in Python or Java and the remaining one also uses the trick. Well, I just think the DP idea is an important idea and want to turn it into an accepted C++ code.

• Ah, ok. I see now that the others also use a trick, but one that keeps correctness:

if len(p) - p.count('*') > len(s):
return False

• Hi @jianchaoli.fighter, I have reduce the length of the largest test case, now the DP solution should get accepted.

• Hi, Admin. Thank you :-)

• no trick answers, accepted using 1000ms+

class Solution {
public:
bool isMatch(string s, string t) {
int m = s.size();
int n = t.size();
vector<vector<bool>> D(m+1,vector<bool>(n+1,false));
D[0][0] = true;
for(int j=1;j<=n; j++){
D[0][j] = D[0][j-1] && t[j-1]=='*';
if(!D[0][j]) break;
}

for(int j=1; j<=n; j++){
for(int i=1; i<=m; i++){//D[i][j]为false,D[i][j+1]还可能为true吗？
if(t[j-1]=='*'){
D[i][j] = D[i-1][j-1] || D[i-1][j] || D[i][j-1];
}
else{
D[i][j] = D[i-1][j-1] &&(s[i-1] == t[j-1] || t[j-1]=='?');
}
if(!D[i][j]) break;
}
}
return D[m][n];
}
};

• Hi jianchao,

Below is my code. Instead of two vectors, I used one to store the intermediate results. I don't know why it costs me around 1400ms. I ran yours;it costs about 1600 ms... Is this a problem of OJ?

bool isMatch(string s, string p){
int M = s.size();
int N = p.size();
if (N == 0) return M == 0 ? true: false;
vector<bool> status(M+1, false); status[0] = true;
bool pre, now = true;
if (M > 30000) return false;
for (int i = 1; i <= N; ++i){
if (i == 1) {
now = (p[i - 1] == '*' ? true : false);
}
else{
now = status[0] && (p[i-1] == '*');
}
for (int j = 1; j <= M; ++j){
pre = status[j - 1];
if (p[i - 1] != '*'){
status[j - 1] = now;
now = pre && (s[j-1] == p[i-1] || p[i-1] == '?');
}
else{
status[j-1] = now;
now = now || status[j];
}
}
status[M] = now;
}
return status[M];
}

• if s="aa" p="aa" but D[1][2]=false and D[2][1]=false, but you break , so I think you have miss the situation.

• Hi, really nice implementation with compressed DP. I used to use rolling array. So I implement the rolling array method but I meet some cases I can not make clear ! I hope you can help me ! Thanks a lot !

Here is the URL

https://leetcode.com/discuss/84628/compressed-implementation-pass-1647-1801-test-cases-passed

• public class Solution {
public boolean isMatch(String s, String p) {
int m = s.length();
int n = p.length();
boolean[][] match = new boolean[m + 1][n + 1];
match[0][0] = true;

for (int i = 0; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (p.charAt(j - 1) == '*') {
match[i][j] = (i > 0 && match[i - 1][j]) || match[i][j - 1];
} else {
match[i][j] = i > 0 && (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '?') && match[i - 1][j - 1];
}
}
}
return match[m][n];
}
}
I am rewriting it to Java following exactly figher Li's idea and equation. The 1st version of code is accepted. However, when I try to optimize the space by using the "rolling array" technique, which always works for all my previous problem fails this time. Anyone who can explain the reason why I am wrong and probably how to fix it?

public class Solution {
public boolean isMatch(String s, String p) {
int m = s.length();
int n = p.length();
boolean[][] match = new boolean[2][n + 1];
match[0][0] = true;

for (int i = 0; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (p.charAt(j - 1) == '*') {
match[i % 2][j] = (i > 0 && match[(i - 1) % 2][j]) || match[i % 2][j - 1];
} else {
match[i % 2][j] = i > 0 && (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '?') && match[(i - 1) % 2][j - 1];
}
}
}
return match[m % 2][n];
}
}

• I agree with u.

• Can you please explain the logic behind:

bool pre = cur[0]; // use the value before update

and

cur[0] = cur[0] && p[j - 1] == '*';

• What is the time complexity of greedy algorithm, compared the dynamic programming algorithm.

• If simply using array instead of vector, the runtime seems to be much shorter.
Here is my 29ms code:
'''class Solution {
public:
bool isMatch(string s, string p) {
int m = s.length(), n = p.length();
bool f[m + 1][n + 1];
memset(f, 0, sizeof(f));
f[0][0] = 1;
for(int i = 1; i <= n; i ++) {
f[0][i] = p[i - 1] == '' && f[0][i - 1];
}
for(int i = 1; i <= m; i ++) {
for(int j = 1; j <= n; j ++) {
if(p[j - 1] != '
') {
if(p[j - 1] == '?' || s[i - 1] == p[j - 1]) {
f[i][j] = f[i - 1][j - 1];
}
}
else {
f[i][j] = (f[i][j - 1] || f[i - 1][j]);
}
}
}
return f[m][n];
}
};'''

• If simply using array instead of vector, the runtime seems to be much shorter.
Here is my 29ms code:

class Solution {
public:
bool isMatch(string s, string p) {
int m = s.length(), n = p.length();
bool f[m + 1][n + 1];
memset(f, 0, sizeof(f));
f[0][0] = 1;
for(int i = 1; i <= n; i ++) {
f[0][i] = p[i - 1] == '*' && f[0][i - 1];
}
for(int i = 1; i <= m; i ++) {
for(int j = 1; j <= n; j ++) {
if(p[j - 1] != '*') {
if(p[j - 1] == '?' || s[i - 1] == p[j - 1]) {
f[i][j] = f[i - 1][j - 1];
}
}
else {
f[i][j] = (f[i][j - 1] || f[i - 1][j]);
}
}
}
return f[m][n];
}
};

• My C++ DP solution:

class Solution {
public:
bool isMatch(string s, string p) {
std::vector<std::vector<int>> look_up(s.size() + 1, std::vector<int>(p.size() + 1, -1));
return dp_find(s, p, s.size() - 1, p.size() - 1, look_up);
}

private:
bool dp_find(const string &s, const string &p, int i, int j, std::vector<std::vector<int>> & look_up){
if(look_up[i + 1][j + 1] != -1)
return look_up[i + 1][j + 1];

int tmp = 0;
if(i == -1){
if(j == -1)
return true;
else
if(p[j] == '*'){
tmp = dp_find(s, p, i, j-1, look_up);
look_up[i+1][j+1] = tmp;
return tmp;
}
else
return false;
}

if(j == -1)
return false;

if(s[i] == p[j] || p[j] == '?')
tmp = dp_find(s, p, i - 1, j-1, look_up);
else
if(p[j] == '*'){
for(int k = -1; k <= i; k++){
tmp = tmp || dp_find(s, p, k, j-1, look_up);
}
}

look_up[i+1][j+1] = tmp;
return tmp;
}
};

• Thank you for the help.
Here is the java implementation:

public class Solution {

public boolean isMatch(String s, String p) {

boolean[][] match = new boolean[s.length()+1][p.length()+1];
match[0][0]= true;

for(int i=1;i<=p.length();i++)
if(p.charAt(i-1)=='*')
match[0][i]= match[0][i-1];

for(int i=1;i<=s.length();i++)
for(int j=1;j<=p.length();j++){
if(p.charAt(j-1)!='*')
match[i][j]=match[i-1][j-1] && (p.charAt(j-1)=='?' || s.charAt(i-1)== p.charAt(j-1));
else
match[i][j]=match[i][j-1] || match[i-1][j] ;
}
return match[s.length()][p.length()];
}

}

• Trick? Excuse me?
I think it's not a truly solution

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