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

题目描述
有一种将字母编码成数字的方式：'a->1', 'b->2', ... , 'z->26'。
现在给一串数字，返回有多少种可能的译码结果

方法一：递归求法

求解思路
对于本题目给出的一串数字，并且要返回有多少种可能的译码结果，我们想到用递归的思想进行求解。每次解码一个字符，如果当前字符等于1或者当前字符加上下一个字符合起来小于等于26，则可以一次解码两个字符。如果当前字符未0，因为0没有对应的解码，因此直接丢弃此种情况。

图片说明

解题代码

public class Solution {
    public int solve (String nums) 
    {
        return back(nums.toCharArray(), 0); // 直接返回结果，具体函数实现下面展示
    }
    // 递归函数
    public int back(char[] mynums, int start)
    {
        //当start走到终点时直接返回1
        if(start == mynums.length)
        {
            return 1;
        }
        //当字符为0的时候，0没对应的解码，所以直接返回0 (此路解码废掉)
        if(mynums[start] == '0')
            return 0;
        //每次解码一个字符
        int myres1 = back(mynums,start+1);
        int myres2 = 0;
        //如果当前字符等于1 或者 当前字符加上下一个字符合起来小于等于26 则可以一次解码两个字符
        if((start < mynums.length-1) && (mynums[start] == '1' || (mynums[start] == '2' &&mynums[start+1] <= '6')))
        {
            myres2 = back(mynums,start+2);
        }
        //返回结果
        return myres1 + myres2;
    }
}

复杂度分析
时间复杂度：递归的情况下，其时间复杂度和题目给出的一串数字的长度有关，因此为 $O(N)$
空间复杂度：因为每次解码一个字符需要申请内存空间，因此空间复杂度为 $O(N)$

方法二：动态规划的思想

求解思路
对于本道题目也可以采用动态规划的思想进行求解，我们用dp[i]表示字符串nums中以i个位置结尾的前缀字符串的解码种数。并且我们对一下情况进行讨论，当前字符不等于0时，dp[i]=dp[i-1]，此时将当前位置的一个字符译码。另一种情况为当前字符和前一个字符记为num，如果10<=num<=26，则将两个合并一起译码。根据以上叙述，使用动态规划的思想对本题进行求解。

图片说明

解题代码

import java.util.*;
public class Solution {
    public int solve (String nums) {
        if(nums.length() == 0 || nums.charAt(0) == '0')
            return 0; // 如果是0则直接返回0
        int[] mydp = new int[nums.length()]; // 动态规划思想
        mydp[0] = 1;
        for(int i = 1; i < mydp.length; i++)
        {
            if(nums.charAt(i) != '0')
            {
                mydp[i] = mydp[i-1]; // 将当前位置的一个字符进行译码
            }
            int hynum = (nums.charAt(i-1)-'0')*10 + (nums.charAt(i)-'0'); // 两个字符合并译码
            if(hynum >= 10 && hynum <= 26)
            {
                if(i == 1) // 如果i为1，则mydp[i]相应加一
                {
                    mydp[i] += 1;
                }
                else
                {
                    mydp[i] += mydp[i-2];
                }
            }
        }
        return mydp[nums.length()-1]; // 返回结果即可
    }
}

复杂度分析
时间复杂度：动态规划，一层循环，因此时间复杂度为 $O(N)$
空间复杂度：申请的dp数组需要引入额外的内存地址空间，因此空间复杂度为 $O(N)$