dp solution with explanation


  • 0

    Firstly look at the example given:
    12 can be decoded as "AB" (1 2) or "L" (12). The reason it can be decoded to 2 strings is because 2 can be a single number representing a letter, or 2 can be one digit of 2-digit number 12.

    This is the same for all digits in input. Each digit can either represent a single letter, or be part of 2-digit number.

    If we already know that the first i - 1 digits can be decoded in dp[i - 1] ways, what about the first i digits? There are 2 situations:

    1. the ith digit represents a single letter. Notice that '0' doesn't represent any letter.
      dp[i] = 0; (s.charAt(i - 1) == '0')
      dp[i] = dp[i - 1]; (s.charAt(i - 1) != '0')

    2. the ith digit along with (i-1)th digit represent a single letter.
      int x = Integer.parseInt(s.substring(i - 1,i + 1)); (the 2-digit number)
      Note that x should be a 2-digit number instead of 1 digit (when (i-1)th char is '0');
      if (x >= 10 && x <= 26) dp[i + 1] += dp[i - 1];

    The initial state is the empty input is one way (dp[0] = 1); And the first input char is one way if it's not '0' (dp[1] = s.charAt(0) != '0' ? 1 : 0);

    Because dp[i] is only related to dp[i-1] and dp[i-2], so space complexity can be constant O(1). However, it's not really necessary or very important because taking care of 3 states is a overhead. Solving the problem in clear logic and easy to understand is more important in most cases.

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

Log in to reply
 

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