Decode Ways

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.

Analysis

1. 状态: memo[i]用来记录从i到最后一位有多少种decode方法
2. 转化方程:
   1. 如果s.charAt(i)=='0'，由于0不能打投，所以decode的方法为0
   2. 如果s.charAt(i)!='0'
      1. 从i开始的两个数字<=26: memo[i]=memo[i+1]+memo[i+2]。比如“135”走到1这一位, “13”小于等于26，说明可以1+“35”（方法有memo[i+1]种），或者“13”+“5”（方法有memo[i+2]种）。
      2. 从i开始的两个数字>26: memo[i]=memo[i+1]。比如“335”走到1这一位, “33”大于26，说明只可以3+“35”（方法有memo[i+1]种）。
3. 初始条件: memo最后多记一位为1， 用于方便。memo倒数第二位为0或1
4. 返回值: memo[0], 表示从第0个字母到最后有多少个decode方法

Code

public class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        if (n == 0) return 0;

        int[] memo = new int[n+1];
        memo[n]  = 1;
        memo[n-1] = s.charAt(n-1) != '0' ? 1 : 0;

        for (int i = n - 2; i >= 0; i--)
            if (s.charAt(i) == '0') continue;
            else memo[i] = (Integer.parseInt(s.substring(i,i+2))<=26) ? memo[i+1]+memo[i+2] : memo[i+1];

        return memo[0];
    }
}

Note

• Integer.parseInt(string s): Parses the string argument as a signed decimal integer

Reference

Leetcode