compact c++ solution easy understanding (with explanations)


  • 2
    J
    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.


  • 0
    R

    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?


  • 3
    J

    @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?:
    alt text
    hope this will help!!


  • 0
    R

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


Log in to reply
 

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