# DP Solution: both Forward & Backward

• First, the backward solution

public int numDecodings(String s) {

`````` // validate the input and take care of special cases
if (null == s || s.length() == 0) return 0;

// let's DP~
int n = s.length();
int[] numDecodingsFromIndex = new int[n + 1];

// initialize the last 2 element of numDecodingsFromIndex[]
numDecodingsFromIndex[n] = 1;
numDecodingsFromIndex[n - 1] = Integer.parseInt(s.substring(n - 1)) != 0 ? 1 : 0;

// backwards
for (int j = n - 2; j >= 0; j--) {

int thisDigit = Integer.parseInt(s.substring(j, j+1));

if (0 == thisDigit) {
continue;
} else {
// when 0 != thisDigit, we can cut at this position
numDecodingsFromIndex[j] = numDecodingsFromIndex[j + 1];

if (Integer.parseInt(s.substring(j, j + 2)) <= 26) {
numDecodingsFromIndex[j] += numDecodingsFromIndex[j + 2];
}
}
}
return numDecodingsFromIndex[0];
``````

}

• Then, the forward solution. Coming up with the forward version is very straightforward, especially for DP-newbies like me.

public int numDecodings(String s) {

`````` // validate the input
if (null == s || s.length() == 0) return 0;

// dp: remember every result that has been calculated
int[] numDecodingsFromIndex = new int[s.length()];
// -1 means "has not been calculated yet"
for (int i = 0; i < numDecodingsFromIndex.length; i++) {
numDecodingsFromIndex[i] = -1;
}

return numDecodings(s, 0, numDecodingsFromIndex);
``````

}

private int numDecodings(final String s, int startIndex, int[] numDecodingsFromIndex) {

`````` // if we have crossed the finish line
if (startIndex >= s.length()) {
return 1;
}

// if the result is already there, just get it
if (numDecodingsFromIndex[startIndex] != -1) {
return numDecodingsFromIndex[startIndex];
}

// if not, we need to calculate it
numDecodingsFromIndex[startIndex] = 0;

// the first digit should be between 1~9
if (Integer.parseInt(s.substring(startIndex, startIndex + 1)) != 0) {

numDecodingsFromIndex[startIndex] = numDecodings(s, startIndex+1, numDecodingsFromIndex);

// if the first two digits are between 1~26, then we get a second cut position
if ((startIndex+1 < s.length()) && (Integer.parseInt(s.substring(startIndex, startIndex + 2)) <= 26)) {
numDecodingsFromIndex[startIndex] += numDecodings(s, startIndex + 2, numDecodingsFromIndex);
}
}

return numDecodingsFromIndex[startIndex];
``````

}

• Please update code format.

Select all code then click on the `{}` button to preserve code formatting.

• I have tried many times. But it just ignored the first and last line. Do you know why?

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