Java dp solution with constant space


  • 0
    A
    public class Solution {public int numDecodings(String s) {
        if (s == null || s.length() == 0 || s.startsWith("0")) {
            return 0;
        }
        int pre_1_cnt = 1;
        int pre_2_cnt = 1;
        int num1 = 0, num2 = 0, cur_cnt = 1;
        /*
        transitional function: cnt(i) = cnt(i-1) + cnt(i-2)
        note: 
        to account for cnt(i-1), num[i] must be in the valid range [1, 9]
        to account for cnt(i-2), num[i-1, i] must be in the valid range[10, 26]    
        */ 
        for (int i = 1; i < s.length(); i++) {
            cur_cnt = 0;
            num1 = Integer.valueOf(s.substring(i, i+1));
            num2 = Integer.valueOf(s.substring(i-1, i+1));
            if (num1 > 0) {
                cur_cnt += pre_1_cnt;
            }
            if (num2 >= 10 && num2 <= 26) {
                cur_cnt += pre_2_cnt;
            }
            pre_2_cnt = pre_1_cnt;
            pre_1_cnt = cur_cnt;
        }
        return cur_cnt;
    }

Log in to reply
 

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