Sharing c++ - memoization


  • -1
    I
    // for memoization
    unordered_map<string,int> m;
    
    // recursive solution with memoization
    // zero sized string or string starts with 0 = 0 way
    // size one string = 1 way 
    // size >= 2
    // - if the first two char is between 10 and 26, we call numDecoding with s.substr(1) and s.substr(2)
    // - else call numDecoding with s.substr(1)
    int numDecodings(string s) {
        if (s.size() == 0 || s[0] == '0') return 0;
        if (s.size() == 1) return 1;
        if (m.find(s) != m.end()) return m[s];
    
        int num = stoi(s.substr(0, 2));
        if (num >= 10 && num <= 26) 
        {
            int t = numDecodings(s.substr(1)) + ((s.size() == 2) ? 1 : numDecodings(s.substr(2)));
            m[s] = t;
            return t;
        } 
        else 
        {
            int t = numDecodings(s.substr(1));
            m[s] = t;
            return t;
        }
    }

Log in to reply
 

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