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

O(N), O(N) dp

可以优化空间复杂度为O(1),

先可以考虑问题中不含有0的情况例如1223

1223的个数 = 122的个数 + 12的个数*(23 <= 26 ? 1 : 0);

新建dp, dp[i]表示以nums[i]结尾的字符串的译码结果的个数;

所以可以得到递推公式dp[i] = dp[i-1] + dp[i-2] (判断为1或0); (所以空间复杂度可以优化，不用一个数组存储，只需要两个指针)，初始化dp[0], dp[1];

然后加入0，首先应该明确两个相邻的0，是一定不可的，直接返回0

然后当nums[i]为0时，> 20 也不可，没有对应的字母,返回0；

特别注意，10，20 时，此时，dp[i] = dp[i-2]; 因为0没有对应的字母;

	import java.util.*;

    public class Solution {
        /**
         * 解码
         * @param nums string字符串 数字串
         * @return int整型
         */
	public int solve (String nums) {
    // write code here
    //0-9, 0的情况
    //dp[i]表示以nums[i]结尾的字符串的译码结果的个数
    
    int[] dp = new int[nums.length()];
    //初始化
    dp[0] = nums.charAt(0) == '0' ? 0 : 1;
    if(nums.length() == 1) return dp[0];
    
    if(nums.charAt(1) != '0' ) dp[1] = dp[0];//加一位数
    int a =  Integer.parseInt("" + nums.charAt(0) + nums.charAt(1));
    if(a >= 10 && a <= 26) dp[1] ++;//一个两位数
    
    for(int i = 2; i < nums.length(); i++){
        if(nums.charAt(i) == '0'){
            if(nums.charAt(i-1) == '0') return 0;//找不到译码
            if(nums.charAt(i-1) > '2') return 0;//找不到译码
            else dp[i] = 0;//10, 20 mark
        }else{
            dp[i] = dp[i - 1];
        }
        
        int tmp = Integer.parseInt("" + nums.charAt(i-1) + nums.charAt(i));
        if(tmp >= 10 && tmp <= 26){
            dp[i] += dp[i-2];
        }
    }
    
    return dp[nums.length() - 1];
}
}