Java clean DP solution with explanation


  • 136
    Y

    I used a dp array of size n + 1 to save subproblem solutions. dp[0] means an empty string will have one way to decode, dp[1] means the way to decode a string of size 1. I then check one digit and two digit combination and save the results along the way. In the end, dp[n] will be the end result.

    public class Solution {
        public int numDecodings(String s) {
            if(s == null || s.length() == 0) {
                return 0;
            }
            int n = s.length();
            int[] dp = new int[n+1];
            dp[0] = 1;
            dp[1] = s.charAt(0) != '0' ? 1 : 0;
            for(int i = 2; i <= n; i++) {
                int first = Integer.valueOf(s.substring(i-1, i));
                int second = Integer.valueOf(s.substring(i-2, i));
                if(first >= 1 && first <= 9) {
                   dp[i] += dp[i-1];  
                }
                if(second >= 10 && second <= 26) {
                    dp[i] += dp[i-2];
                }
            }
            return dp[n];
        }
    }

  • 9
    N

    nice solution! I rewrote in C++

     int numDecodings(string s) {
        int n = s.size();
        if (n == 0 || s[0] == '0') return 0;
        if (n == 1) return 1;
        int pre2 = 1, pre1 = 1;
        int cur;
        for (int i = 1; i < n; ++i) {
            cur = 0;
            int first = (s[i] - '0');
            int second = stoi(s.substr(i - 1, 2));
            if (1 <= first && first <= 9)
                cur += pre1;
            if (10 <= second && second <= 26)
                cur += pre2;
            pre2 = pre1;
            pre1 = cur;
        }
        return cur;
    }

  • 2

    I prefer you solution which I think is more intuitive. Thanks for sharing!


  • 0
    N

    When we do =>

    if (s.length() == 0)
       return 0;
    

    Why do you say dp[0] means an empty string will have one way to decode? Empty string has 0 ways to decode correct?

    Why do we need dp[0] to be 1 and not zero?


  • 4
    E

    @piyushsharma Agree with the first comment. As for the second one, it is easy to understand with the provided example. Let's say you want to decode "12". Before the loop, dp[] array becomes [1,1,0]. Then when i = 2, first is 2, second is 12, both can be decoded. So dp[2] = dp[1] + dp[0], which is 2. If you initialize dp[0]=0, then the answer becomes 1, which is incorrect.


  • 10
    N

    @ElaricY Thank you for the answer. I can see that we need dp[0] = 1 for the correct solution. Just want to clarify that dp[0] = 1 is just an initialization to make sure our solution works for all strings for lengths >= 2. The point I am trying to make is dp[0] is not the number of ways to decode an empty string, it is an initialization as strings with length 0 or 1 will not even enter the loop.


  • 0
    G

    Can anyone please explain why we are doing :

    dp[i] += dp[i-1]; // In the first if statement.
    and
    dp[i] += dp[i-2]; //In the second if statement.

    Thanks.


  • 0
    Z

    nice and clean solution!!!


  • -1
    S

    Why you didn't check if dp[1] is between 1~9. Modified a little bit

    public class Solution {
        public int numDecodings(String s) {
            if (s == null || s.length() == 0) return 0;
            
            int []dp = new int[s.length() + 1];
            dp[0] = 1;
            if (s.charAt(0) > '0' && s.charAt(0) <='9') {
                dp[1] = 1;
            }else{
                dp[1] = 0;
            }
            
            for(int i=2; i<=s.length(); i++){
                int one = Integer.parseInt(s.substring(i-1, i));
                int two = Integer.parseInt(s.substring(i-2, i));
                if (one >=1 && one <=9){
                    dp[i] += dp[i-1];
                }
                if (two >=10 && two <=26){
                    dp[i] += dp[i-2];
                }
            }
            
            return dp[s.length()];
        }
    }
    

  • 3
    M

    @yfcheng
    great solution, but explanation is not perfect.
    I mean, you do

    if(s == null || s.length() == 0) {
    return 0;

    and then you say dp[0] = 1. Which is wrong.

    Further, you are making a assignment operation as an addition operation
    dp[i] += dp[i-1];
    which can be replaced by
    dp[i] = dp[i-1]


  • 0
    M
    This post is deleted!

  • 0
    F

    This is My Solution, a little bit modification:

    public int numDecodings(String s) {
    	if (s == null || s.length() == 0 || s.charAt(0) == '0') {
    		return 0;
    	}
    
    	char[] cs = s.toCharArray();
    	int[] dp = new int[cs.length + 1];
    	dp[0] = 1;
    	dp[1] = 1;
    
    	for (int i = 1; i < cs.length; i++) {
    		int two = Integer.valueOf("" + cs[i - 1] + cs[i]);
    		if (cs[i] != '0') {
    			dp[i + 1] = dp[i];
    		}
    		if (two >= 10 && two <= 26) {
    			dp[i + 1] += dp[i - 1];
    		}
    		if (dp[i] == 0)
    			break;
    	}
    	return dp[cs.length];
    }

  • 0
    D

    My solution with explanation, no need to check further if the sequence is invalid

    public class Solution {
        public int numDecodings(String s) {
            // invalid sequence
            if (s == null || s.length() <= 0 || s.charAt(0) == '0') { return 0; }
            
            int[] dp = new int[s.length() + 1];
            // init
            dp[0] = 1;
            dp[1] = 1;
            
            int i = 2;
            for (; i < dp.length; i++)
            {
                // current character
                char end = s.charAt(i - 1);
                if (end == '0')
                {
                    
                    char pre = s.charAt(i - 2); 
                    // invalid sequence if character right before '0' is not '1' or '2' 
                    // no need to check further
                    if (pre != '1' && pre != '2') { return 0; }
                    
                    dp[i] = dp[i - 2];
                }
                else
                {
                    dp[i] = dp[i - 1];
                    // 2 digits in range (10, 20) (20, 26] is valid
                    int num = Integer.parseInt(s.substring(i - 2, i));
                    if (num > 10 && num < 20 || num > 20 && num <= 26)
                    {
                        dp[i] += dp[i - 2];
                    }
                }
            }
            
            return dp[i - 1];
        }
    }
    

  • 1

    one scenario I do not understand is for example I have "01", which I suppose to have decode way of 1 (0 | 1), now that "1" is valid, dp[2] = 0 + dp[1] where dp[1] is 0, I got dp[2] is 0... I am confused here, it must be something wrong of how I analyze, can someone help?


  • 0
    J

    @vinnie2 I think for "01", the result would be 0


  • 0

    @vinnie2 If there is nothing in front of "01", it is an invalid input string itself. If there is additional numbers in front of "01", "0" has to be considered together with the number before it, instead of being considered as the first digit of a new letter.


  • 0
    O
    This post is deleted!

Log in to reply
 

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