# Accepted Straightforward Memoization C++ Solution (Without cheating/tricks)

• ``````vector<int> memo;
// 0 corresponds to value has been not set , 1 corresponds to true and 2 corresponds to false

bool helper(string &s,string &p,int pos1,int pos2,int &len1,int &len2){
bool val=false;

if(pos1==len1 && pos2==len2) {return true;} // base case

int index=pos1*10+pos2; // if pos1=1 and pos2=2 then index of memorization vector will be 12
if(memo[index]!=0) // zero corresponds to not set
return memo[index]==1; // 1 corresponds to true
//-----------------------------------------------------------------------------------------
bool in=false; // just to check if any case below for '*' was entered
// Cases for '*'
if(pos1<len1 && s[pos1]=='*'){
in =true;
for(int i=pos2;i<=len2;i++){
val=helper(s,p,pos1+1,i,len1,len2);
if(val) {memo[index]=1; return true;}
}
}
if(pos2<len2 && p[pos2]=='*'){
in=true;
for(int i=pos1;i<=len1;i++){
val=helper(s,p,i,pos2+1,len1,len2);
if(val) {memo[index]=1; return true;}
}
}
if(in){ memo[index]=2; return false;}

//-----------------------------------------------------------------------------------------
// Case for not '*'
if(pos1<len1 && pos2<len2){
val= (s[pos1]==p[pos2] || s[pos1]=='?' || p[pos2]=='?') && helper(s,p,pos1+1,pos2+1,len1,len2);

if(val) { memo[index]=1; return true; }
else { memo[index]=2; return false; }
}

else { return false; }
}

bool isMatch(string s, string p) {
int len1=s.length(); int len2=p.length();
memo=vector<int>(((len1)*10 + (len2)),0);
int pos1=0,pos2=0;
return helper(s,p,pos1,pos2,len1,len2);
}``````

• Would you please explain this part of the code:

Blockquote
int index=pos1*10+pos2; // if pos1=1 and pos2=2 then index of memorization vector will be 12
Blockquote

Doesn't this rely on the assumption that pos2 < 10?

• That's a good pick. I'll look into it. Basically I need to form a unique key given two integers. Since indices will always be positive, I can use cantor pairing function for the task. So key(pos1,pos2) = 1/2 (pos1+pos2) (1+pos1+pos2) + pos2 . One shall then use an unordered map instead of a vector for memoization.

• why just use a[k][j] to memorize this data.

• this problem has some test case that didn't allow use this memorization strategy:

such as "aaaaaaaaaaa..............."

the correct version should be mem[i][j] or mem[s * p.length() + p], both of them will cause memory limit exceed

if you use map<int, set<int>> (c++ means unordered here) it will cause time limit exceed

so the version you give is a tricks and lucky.....

Or you can think that the test case is so extreme, and we may need other advance algorithm, or just use a better machine...

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