题解 | #把数字翻译成字符串#

import java.util.*;

/**
 * NC116 把数字翻译成字符串
 * @author d3y1
 */
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 解码
     * @param nums string字符串 数字串
     * @return int整型
     */
    public int solve (String nums) {
        return solution(nums);
    }

    /**
     * 动态规划
     *
     * dp[i]表示前i位数字的译码种数
     * 
     *         { 0                  , 单双数字均不可译码
     * dp[i] = { dp[i-2]            , 仅双位数字可以译码
     *         { dp[i-1]            , 仅单位数字可以译码
     *         { dp[i-1] + dp[i-2]  , 单双数字均可以译码
     *
     * @param nums
     * @return
     */
    private int solution(String nums){
        int len = nums.length();
        if(len == 0){
            return 0;
        }
        if(len == 1){
            if("0".equals(nums)){
                return 0;
            }else{
                return 1;
            }
        }

        int[] dp = new int[len+1];
        // 初始化
        dp[0] = 1;
        dp[1] = 1;
        int dDigit,sDigit;
        for(int i=2; i<=len; i++){
            // 双位数字 double digit
            dDigit = Integer.parseInt(nums.substring(i-2, i));
            // 单位数字 single digit
            sDigit = Integer.parseInt(nums.substring(i-1, i));
            // 当前第i位数字为0 单位数字不可译码
            if(sDigit == 0){
                // 超出字母范围 双位数字不可译码
                if(dDigit==0 || dDigit>26){
                    return 0;
                }else{
                    // 双位数字译码
                    dp[i] = dp[i-2];
                }
            }else{
                // 单位数字译码
                dp[i] = dp[i-1];
                // 未超字母范围 双位数字可译码 (注意 01 02 03 04 05 06 07 08 09 不可译码)
                if(10 <= dDigit && dDigit <= 26){
                    // 双位数字译码
                    dp[i] += dp[i-2];
                }
            }
        }

        return dp[len];
    }
}