# C++ Solution with detailed explanation

• 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()];
}
``````

};

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