1ms Java DP solution - O(1) space & O(n) time


  • 0
    L
        public int numDecodings(String s) {
            if(s == null || s.length() == 0 || s.charAt(0) == '0')
                return 0;
    
            int n=s.length();
            if(n == 1) return 1;
    
            int[] dp = new int[3];  //Improved, just store the recent 3 counts
            dp[2] = 1;
            dp[1] = s.charAt(n-1) == '0'? 0: 1;
    
            char curr, pre = s.charAt(n-1);
            for(int i=n-2; i>=0; i--, pre=curr, dp[2]=dp[1], dp[1]=dp[0] /*rotate values in dp*/) {
                curr = s.charAt(i);
                if( curr == '0') {
                    dp[0] = 0;
                    continue;
                } else if ( curr=='1' || (curr=='2' && pre>='0' && pre<='6' )) {
                    dp[0] = dp[1] + dp[2];
                } else {
                    dp[0] = dp[1];
                }
            }
    
            return dp[0];
        }
    

Log in to reply
 

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