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


  • 2
    C
    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);
    }

  • 0
    S

    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?


  • 0
    C

    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.


  • 0
    Y

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


  • 0
    N

    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...


Log in to reply
 

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