# DP with easy understand Java Solution

• ``````public class Solution {
public int numDecodings(String s) {
int n = s.length();
if (n == 0 || s.startsWith("0")) {
return 0;
}
int[] ways = new int[n+1];
ways[0] = 1;
ways[1] = 1;
for (int i = 2; i <= n; i++) {
int first = Integer.parseInt(s.substring(i-2, i));
int prev = (first <= 26 && first > 9) ? ways[i-2]:0;
int plus = (Integer.parseInt(s.substring(i-1, i)) == 0) ? 0:ways[i-1];
ways[i] = prev + plus;
}
return ways[n];
}
}``````

• Exact idea as above with some better named variables to follow the logic

``````public int numDecodings(String s) {

if(s== null || s.isEmpty() || s.charAt(0) == '0') return 0;
int[] dp = new int[s.length()+1];
dp[0] = 1;
dp[1] = 1;

for(int i = 2 ; i <= s.length() ;i++){
int num = Integer.parseInt(s.substring(i-2,i));
int twoStepsBehind = (num <= 26 && num >= 10) ? dp[i-2] : 0;
int oneStepBehind = (Integer.parseInt(s.substring(i-1,i)) != 0) ? dp[i-1] : 0;
dp[i] = twoStepsBehind + oneStepBehind; // can reach here by either hopping 2 steps or 1 step
}

return dp[s.length()];

}``````

• @sj482 Your solution is fantastic. Here's a mildly refactored version of the same:

``````	public int numDecodings(String s) {
if (s == null || s.isEmpty()) return 0;
int n = s.length();
int[] dp = new int[n + 1];
dp[0] = 1; // if no characters, there's only 1 decoding
if (s.charAt(0) == '0') return 0; // whoops! your first character turned out to be a dud
dp[1] = 1; // if 1 character, there's only 1 decoding. We've already vetted it's not a 0
for (int i = 2; i <= n; i++) {

int numUsingLast2Chars = Integer.parseInt(s.substring(i - 2, i));
int numUsingLast1Char = Integer.parseInt(s.substring(i - 1, i));

if (isValidTwoDigitNumber(numUsingLast2Chars)) {
dp[i] += dp[i - 2];
}
if (isValidOneDigitNumber(numUsingLast1Char)) {
dp[i] += dp[i - 1];
}
}

return dp[n];
}

private boolean isValidOneDigitNumber(int numUsingLast1Char) {
return numUsingLast1Char != 0;
}

private boolean isValidTwoDigitNumber(int numUsingLast2Chars) {
return numUsingLast2Chars >= 10 && numUsingLast2Chars <= 26;
}
``````

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