C++ Solution with detailed explanation


  • 0
    S

    In this question we initilze the table to s.size()+1
    s[0]=1

    The dynamic equation
    f[i]=f[i-1]+f[i-2]

    for Example 1 2 1
    table : 1 1 2 3

    	   The answer is 3
    

    *** The most difficult part of this question is how to handle 0***

    Case 0123
    The answer is 0

    Case 0
    The answer is also 0

    Case 1: We consider the the i th element is 0
    2 1 1 1
    table 1 1 2 3 5

             2 1 1 1 0
    

    table 1 1 2 3 5 3

    If the ith element is 0 and the i-1 is 1 or 2 then
    f[i]=f[i-2]

    Case 2: ith element is 0 and i-1th element is 0 of >2
    2 1 1 3 0
    table 1 1 2 3 5 0

             2 1 1 0 0
    

    table 1 1 2 3 2 0

    Case 3 we need to consider if the i-2 and i-1 is > 26
    2 1 1 3 1
    table 1 1 2 3 5 5

    If i-2 and i-1 is larger than 26 then f[i]=f[i-1]

    Otherwise f[i]=f[i-1]+f[i-2]

    THE END

    class Solution {
    public:
    /**
    * @param s a string, encoded message
    * @return an integer, the number of ways decoding
    */
    int numDecodings(string& s) {
    // Write your code here
    if(s.size()==0)
    return 0;
    vector<int> table(s.size()+1);

        //Initialize table
        table[0]=1;
        if(s[0]!='0')
           table[1]=1;
        else
           return 0;
           
        //Dynamic Equation 
        for(int i=2;i<table.size();i++){
           //Case 1: where i-1 is 0, then we can't decode 
            string tmp=s.substr(i-2,2);
            int sum=stoi(tmp); 
            
            if(s[i-1]=='0'){
               if(s[i-2]=='0' || s[i-2]>'2')
                 table[i]=0;
               else
                 table[i]=table[i-2];
            }
            //Case 2: we check if the i-1 and i-2 is larger than 26 
            else if(s[i-2]=='0'||sum>26)
              table[i]=table[i-1];
            else
              table[i]=table[i-1]+table[i-2];
        }
        
        return table[s.size()];
    }
    

    };


Log in to reply
 

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