# Java clean DP solution with explanation

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

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

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

• 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?

• @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.

• @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.

• 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.

• nice and clean solution!!!

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

• @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]

• This post is deleted!

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

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

• 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?

• @vinnie2 I think for "01", the result would be 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.

• This post is deleted!

• How can we print all the possible decoded string using above solution ?

• Beautiful solution! easy to understand.

• Thank you so much for this clean and intuitive solution!!

I wrote some notes for myself reference, hope it might help someone to understand this solution.

dp[i]: represents possible decode ways to the ith char(include i), whose index in string is i-1

Base case: dp[0] = 1 is just for creating base; dp[1], when there's one character, if it is not zero, it can only be 1 decode way. If it is 0, there will be no decode ways.

Here only need to look at at most two digits before i, cuz biggest valid code is 26, which has two digits.

For dp[i]: to avoid index out of boundry, extract substring of (i-1,i)- which is the ith char(index in String is i-1) and substring(i-2, i)

First check if substring (i-1,i) is 0 or not. If it is 0, skip it, continue right to check substring (i-2,i), cuz 0 can only be decode by being together with the char before 0.

Second, check if substring (i-2,i) falls in 10~26. If it does, means there are dp[i-2] more new decode ways.

Time: should be O(n), where n is the length of String
Space: should be O(n), where n is the length of String

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