Decode Ways

leetcode 91.

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.

For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

The number of ways decoding "12" is 2.

Solution. This is another dp problem. If we want to compute str[X1, X2, …, Xi-2, Xi-1, Xi].

1. Check if Xi is a valid one letter number.
If it is, str[X1, X2, …, Xi-2, Xi-1, Xi] += str[X1, X2, …, Xi-2, Xi-1]

2. Check if Xi-1Xi is a valid two letter number.
If it is, str[X1, X2, …, Xi-2, Xi-1, Xi] += str[X1, X2, …, Xi-2]

public static int numDecodings(String s) {
    if (s.length() == 0 || s.charAt(0) == '0') {
        return 0;
    }
    int[] dp = new int[s.length() + 1];
    dp[0] = 1;
    dp[1] = 1;
    for (int i = 1; i < s.length(); i++) {
        int oneLetterNum = Integer.parseInt(s.substring(i, i + 1));
        if (oneLetterNum > 0) {
            dp[i + 1] += dp[i];
        }
        int twoLetterNum = Integer.parseInt(s.substring(i - 1, i + 1));
        if (twoLetterNum >= 10 && twoLetterNum <= 26) {
            dp[i + 1] += dp[i - 1];
        }
    }
    System.out.println(Arrays.toString(dp));
    return dp[s.length()];
}

Check my code on github.