DP solution and some clarification


  • 0
    N

    I believe the description has below indication
    1.every encoding ways which may have isolated '0' is invalid, should not be counted
    so take "10" as a case, we could parse it into (1, 0) and (10). However (1, 0) is not valid, so this string only has 1 encoding way
    and for the "010" , the encoding way is 0. because all the partition ways would have isolated 0.

    2.empty string indicate 0 way

    However for the DP to correctly working, we should define table[0] as 1,

    class Solution {
    public:
        int numDecodings(string s) {
            if (s.length() == 0 || s[0] == '0') return 0;
            vector<int> table (s.length() + 1, 0);
            int tmp1, tmp2;
            table[0] = 1;
            table[1] = s[0] != '0' ? 1 : 0; 
            
            for (int i = 2; i <= s.length(); i++) {
                tmp1 = stoi(s.substr(i - 1, 1));
                tmp2 = stoi(s.substr(i - 2, 2));
                if (1 <= tmp1 && tmp1 <= 9) {
                    table[i] += table[i - 1];
                }
                
                if ( 10 <= tmp2 && tmp2 <= 26) {
                    table[i] += table[i - 2];
                }
            }
            
            return table[s.length()];
    
        }
    };
    

Log in to reply
 

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