Java: 10 lines DP with O(n) time and O(1) space beats 91%


  • 1
    F
    public int numDecodings(String s) {
        if (s == null || s.length() == 0) return 0;
        int dp0 = 1, dp1 = s.charAt(0) > '0' ? 1 : 0, dp2;
        for (int i = 1; i < s.length(); i++) {
            dp2 = 0;
            if (s.charAt(i) > '0') dp2 += dp1;
            if (s.charAt(i - 1) == '1' || (s.charAt(i - 1) == '2' && s.charAt(i) < '7')) dp2 += dp0;
            dp0 = dp1;
            dp1 = dp2;
        }
        return dp1;
    }

Log in to reply
 

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