# JAVA DP solution

• ``````public class Solution {
public int numDecodings(String s) {
/*corner case: when the first char is '0', we cannot decode the string*/

if(s == null || s.length() == 0 || s.charAt(0) == '0') return 0;
/*To update the subproblem, we only need the last state and the state before last state*/
int[] dp = new int[2];
dp[0] = 1;
dp[1] = 1;
for(int i = 1; i < s.length(); i++){
int temp = s.charAt(i) - '0';
/*If the number at current position is 0, and the last number is 0 too, we cannot decode the string. Also, if the last number is greater than 2, we cannot decode the string*/
if(temp == 0){
if(s.charAt(i-1) == '0' || s.charAt(i-1) > '2') return 0;
}
else{
/*If the current number is non-zero, but the last number is zero, we could not have more ways to decode the string. So the current state is based on the last state.*/
if(s.charAt(i-1) == '0') {
dp[i%2] = dp[(i-1)%2];
}
/*If the current number is non-zero, and could combine with the last number to get a number less than or equal to 26, we could have two ways to decode.*/
else if(10*(s.charAt(i-1) - '0') + temp <= 26){
dp[i%2] += dp[(i-1)%2];
}
/*If the current number is non-zero, but could not combine with the last number to get a number less than or equal to 26,the current state is based on the last state.*/
else{
dp[i%2] = dp[(i-1)%2];
}
}
}
return dp[(s.length() -1)%2];

}
}
``````

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