Simple and easy understand c++ code with full explanation


  • 1
    A

    This problem is similar with "climb stairs", but I was stuck in this problem because I didn't fully understand the idea.

    The key to this problem is how to choose the strategy for the next move.
    Assume S is the string and S1 is a substring of S that we know the number of combinations. Then there are two ways we can move to next step: either append one number or two numbers. That is [S1, XY] or [S1X, Y], where X and Y are new numbers and ',' is the separator. We only need to know if 'Y' itself is valid or a combination of 'XY' is valid. If 'Y' is valid, then the current result should add the answer of [S1X]; if 'XY' is valid, we need to add the answer of [S1].

        int numDecodings(string s) { 
            int c1, c2, c3;
            c1 = c2 = 1;
            c3 = 0;
            if (s.size() == 0) return 0;
            if (s[0] == '0') return 0;
            for (int i = 1; i < s.size(); ++i) {
                c3 = 0;
                int v = (s[i-1]-'0')*10 + s[i]-'0';
                if (v > 9 && v <= 26) //choose [S1,XY], S1 is a substring of S
                    c3 += c1;
                if (s[i] != '0') //choose [S1X, Y] or [S1, X, Y] 
                    c3 += c2;
                c1 = c2;
                c2 = c3;
            }
            return c2;
        }
    

Log in to reply
 

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