Concise and short c++ DP solution, with explanation


  • 0
    int numDecodings(string s) {
        int64_t a = 1, b = ways(s[0]);
    
        for (int i = 1; i < s.size(); i++) {
            int64_t c = ways(s[i]) * b // ways that s[i] decodes separately
                + ways(s[i - 1], s[i]) * a; // ways that s[i-1] and s[i] decode together
            a = b;
            b = c % (int)(1e9 + 7);
        }
    
        return b;
    }
    
    int ways(char c) {
        // 0: invalid
        // *: any of 1~9
        // 1~9: one
        return c == '0' ? 0 : c == '*' ? 9 : 1;
    }
    
    int ways(char a, char b) {
        if (a == '*')
            // **: any of 11~19 or 21~26
            // *0~*6: two, one from 10~16 and the other from 20~26
            // *7~*9: one from 17~19
            return b == '*' ? 15 : b <= '6' ? 2 : 1;
    
        if (a == '1')
            // 1*: any of 11~19
            // 10~29: one
            return b == '*' ? 9 : 1;
    
        if (a == '2')
            // 2*: any of 21~26
            // 20~26: one
            // 27~29: invalid
            return b == '*' ? 6 : b <= '6' ? 1 : 0;
    
        // 0x, 3x~9x: invalid
        return 0;
    }
    

Log in to reply
 

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