compact c++ solution easy understanding (with explanations)

• ``````class Solution {
public:
int numDecodings(string s) {
if(s.size()==0 || s[0]=='0')return 0;
int f[3]={0, 1, 1};
for(int i=1; i<s.size(); i++){
f[0]=f[1];f[1]=f[2];
f[2]=f[1]*(s[i]!='0') + f[0]*(s[i-1]!='0' && (s[i-1]-'0')*10+s[i]-'0' <= 26);
}
return f[2];
}
};
``````

Assume that we know f(k-1) and f(k), then
case 1:
if the next digit is non-zero and can attach to the k-th digit to forge a legal combination. then f(k+1) = f(k-1)+f(k)

case 2:
if the k+1th digit is zero then it have to attach to the previous digit to forge a legal combination, if it is not legal when attached to the previous digit, then the sequence can't decoded in any way, thus f(k+1)=0 and should return 0, else if it in fact can be attached to the previous digit then f(k+1)=f(k-1)

case 3: if the k+1the digit is non-zero but can't attach to the previous digit, then f(k+1)=f(k)

`f[2]=f[1]*(s[i]!='0') + f[0]*(s[i-1]!='0' && (s[i-1]-'0')*10+s[i]-'0' <= 26);`

in the above code f[2] denotes f(k+1), f[1] denotes f(k) and f[0] denotes f(k-1), s[i]!=0 means that s[i] can be mapped to one of the alphabet, (s[i-1]!='0' && (s[i-1]-'0')*10+s[i]-'0' <= 26) means s[i] can be attached to previous number to form a new number that can have a map to the alphabet.

• Can I ask you why you initialize the array with `int f[3]={0, 1, 1};`. In DP, does the first character (if non-zero) have the value of 1 in the DP array since it can be decoded? Could you please give me details as the how the state transitions are working?

• @rahul172
Introduce a g(x) as a map from position to decode ways, we know that g(0) = 1 given that the first digit is not '0'. that's why f[2] = 1. We can easily list what g(1) could be based on the s[1] character. if we want to generalize the state transition process I would require that g(-1) = 1(although g(-1) doesn't make sense),and that's why f[1]=1. We actually don't care what g(-2) is, so you can basically set anything to f[0]. f[2] actually means f(K+1), f[1] means f(K) and f[0] f(K-1), in the 3 cases as I explained we need f(K-1), f(K) to compute f(K+1), but we don't take that memory so we can take f[0-3] as a sliding window to store f(K-1), f(K), f(K+1)
I suppose this can be regard as a state transition process?:

hope this will help!!

• @jerrik Thank you so much! I appreciate the effort! I hope you get more up-votes. I up-voted you!

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