C++ My DP solution beats 0.09% of cpp submissions.. What's so wrong with mine T_T


  • 0
    W
    class Solution 
    {
    public:
        int numDP(string s, int start, vector<int>& memo)
        {
            if (start == s.size()) return 1;
            if (memo[start] != 0) return memo[start];
            
            int count = 0;
            int num = stoi(s.substr(start, 1));
            if (num > 0 && num <= 9)
            {
                count = numDP(s, start+1, memo);
                
                if (start + 2 <= s.size())
                {
                    num = stoi(s.substr(start, 2));
                    if (num > 0 && num <= 26)
                        count += numDP(s, start+2, memo);
                }
            }
            
            memo[start] = count;
            return memo[start];
        }
        int numDecodings(string s) 
        {
            if (s.empty()) return 0;
            vector<int> memo(s.size(), 0);
            return numDP(s, 0, memo);
        }
    };

  • 0
    T

    Your algorithm is not DP... DP solutions need to store numDP(s, start) in an array.


  • 0
    W

    It does store it in this line
    memo[start] = count;


Log in to reply
 

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