# dp solution with explanation

• 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];
}
}
``````

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