1. Description

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.

2. Example

Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).
The number of ways decoding "12" is 2.

3. Explanation

Let dp[i] stands for the number of ways decoding s(0, i)

(1). dp[0] = 1
(2). dp[1] =
\begin{cases}
1, \quad \text{if} \quad s(0,1) \gt 26 || s[1] == 0 \
2, \quad \text{if} \quad s(0,1) \le 26 \& \& s[1] !=0
\end{cases}
(3). dp[i] =
\begin{cases}
dp[i - 1], \quad \text{if} \quad s(i-1,i) \gt 26 || s[i] == 0 \
dp[i - 1] + dp[i - 2], \quad \text{if} \quad s(i-1,i) \le 26 \& \& s[i] !=0
\end{cases}

4. Code

public class LeetCode0091 {
    public int numDecodings(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }

        int[] dp = new int[s.length() + 1];
        dp[0] = 1;

        int pre = s.charAt(0) - '0';

        if (pre == 0) {
            return 0;
        } else {
            dp[1] = dp[0];
        }

        for (int i = 1; i < s.length(); i++) {
            int current = s.charAt(i) - '0';
            int num = pre * 10 + current;

            if (num == 0 || current == 0 && pre > 2) {
                return 0;
            }
            if (num == 10 || num == 20) {
                dp[i + 1] = dp[i];
            } else {
                dp[i + 1] = dp[i];
                if (num < 27 && num > 10) {
                    dp[i + 1] += dp[i - 1];
                }
            }
            pre = current;
        }
        return dp[s.length()];
    }

    public static void main(String[] args) {
        LeetCode0091 leetcode = new LeetCode0091();
        System.out.println(leetcode.numDecodings("1212"));
    }
}