another C++ DP solution with comments


  • 0
    G
    class Solution {
    public:
    
        #define IS_FIRST_CHARACTER() i == 1
        #define ARE_FIRST_CHARACTERS() i == 2
    
        int numDecodings(string s) 
        {
            if(s.empty())
            {
                return (0);
            }
            
            //
            // memoization table
            //
            
            vector<int> D(s.size() + 1,0);
            
            for(int i = 1; i <= s.size(); ++i)
            {
                //
                // First look at the current char and
                // decide if it is legal, if yes then just return
                // the number from the previous character
                //
                
                if(s[i - 1] >= '1' && s[i - 1] <= '9')
                {
                    D[i] = (IS_FIRST_CHARACTER() ? 1 : D[i - 1]);
                }
                
                //
                // The second phase is to check two consecutive characters
                // if together they are legal then we can add their result
                //
                
                if(i > 1 && ((s[i - 2] == '1' && s[i - 1] <= '9') || (s[i - 2] == '2' && s[i - 1] <= '6')))
                {
                    D[i] += (ARE_FIRST_CHARACTERS() ? 1 :  D[i - 2]);
                }
            }
            
            return (D[s.size()]);
        }
    };
    

Log in to reply
 

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