DP, Java and constant space. Easy to understand


  • 0
    A
    public int numDecodings(String s) {
        int n = s.length();
        if (n == 0 || s.charAt(0) == '0')
            return 0;
        int dp1, dp2, dp3;
        dp1 = dp2 = dp3 = 1;
        int a, b;
        for (int i = 2; i <= n; i++) {
            a = s.charAt(i - 1) - '0';
            b = s.charAt(i - 2) - '0';
            dp3 = a != 0 ? dp2 : 0;
            if (b > 0 && b < 2 || a >= 0 && a <= 6 && b == 2) dp3 += dp1;
            dp1 = dp2;
            dp2 = dp3;
        }
        return dp3;
    }

Log in to reply
 

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