把数组翻译成字符串

题目：把数字翻译成字符串
描述：有一种将字母编码成数字的方式：'a'->1, 'b->2', ... , 'z->26'。现在给一串数字，返回有多少种可能的译码结果。注意到该题目中并未出现数字0对应的字母，当给定的数字串中出现0时，要根据其位置进行处理，因此这是本题的一个难点。

示例1：输入："12"，返回值：2
说明：输出结果表示存在2种可能的译码结果（”ab” 或”l”）
示例2：输入："31717126241541717"，返回值：192
说明：输出结果表示存在192种可能的译码结果

方法一:动态规划

在手动翻译一串数字时，我们会对数字串的第一个数字寻找对应的字母，接着加入数字串的第二个数字，并且寻找其对应的字母，当然为了得到更多的译码结果我们会对第一个数字和第二个数字组成的数寻找对应的字母，不过此时这个数必须小于等于26，否则没有对应的字母，接着我们在前面的翻译结果下，加入数字串的第三个数字以及第四个数字，以此类推，直到完成所有的数字串。记录之前翻译的结果而对当前翻译有影响的过程即为典型的动态规划过程，因此方法一我们介绍动态规划。上面的分析使我们成功的将问题转换为动态规划的问题，对于一个动态规划问题，我们只需要从两个方面考虑，那就是找出问题之间的联系，以及记录答案。用一句话解释动态规划就是记住之前的结果。解决动态规划通常分为四个步骤：
  • 问题拆解，找到问题之间的联系，即当前问题受到前面问题的影响
  • 状态定义
  • 转移方程推导
  • 具体实现

思路分析+实例

设置$dp[i]$为数字串从左到右第i个数字结尾的当前数字串所拥有的翻译方法数，往前一步，如果拼接成的数在[11,19]或者[21,26]的范围内 ，那么$dp[i] = dp[i-1] + dp[i-2] $；否则$dp[i] = dp[i-1]$；特别的当拼接的数为10或者20时，由于不存在数字0的译码，往前一步不会增加译码数，只有10或者20各自对应的译码，因此$dp[i]=dp[i-2]$最终的译码方法数为$dp[len-1]$，其中$len$表示数字串的长度。将上述分析可归纳为最终的转移方程,如下：
  • 如果$i=0$,$dp[i]=1$
  • 否则如下:
    --如果$nums[i]=0$,如果10或者20出现在开头，则$dp[1]=1$;否则$dp[i]=dp[i-2]$
    --否则如果拼接的数在规定的范围内，$dp[i]=dp[i-1]+dp[i-2]$
    --以上情况均不符合$dp[i]=dp[i-1]$

实例：任意给定数字串：”11227“

11227 当前译码方法数 译码方案 转移方程
1 $dp[0]=1$ 1a
11 $dp[1]=2$
11aa
11k
$i==1$，拼接的数11在范围内，因此$dp[1] =2$
112 $dp[2]=dp[1]+dp[0]=3$
112a
112aab
112kb
 $dp[i] = dp[i-1]+dp[i-2]$
1122 $dp[3]=dp[2]+dp[1]=5$
1122aav
1122kv
1122alb
1122aabb
1122kbb
$dp[i] = dp[i-1]+dp[i-2]$
11227 $dp[4]=dp[3]=5$
11227aavg
11227kvg
11227albg
1227aabbg
11227kbbg
$dp[i]=dp[i-1]$

C++核心代码 

class Solution {
public:
    /**
     * 解码
     * @param nums string字符串 数字串
     * @return int整型
     */
    int solve(string nums) {
        // write code here
        int len=nums.size();
        if(len==0 || nums[0]=='0')//排除掉空数字串以及以0开始的数字串
            return 0;
        vector<int> dp(len,0);//dp[i]用于存储到第i位数字的译码方案数，其中i=0,1,2...len-1
        dp[0]=1;//i=0,第一位数结尾的译码方法数必为1
        for(int i=1;i<len;i++)
        {
            if(nums[i] == '0')
            {
                if(nums[i-1] =='1'||nums[i-1] == '2')
                {
                    if(i == 1) dp[i] = 1;//数字串以10或者20开头的情况
                    else dp[i] = dp[i-2];//数字串中存在10或者20的情况下，当前译码数等于后退两步的译码数
                }
            }
            else if(nums[i - 1] == '1' || (nums[i - 1] == '2' && nums[i] >= '1' && nums[i] <= '6'))
            {
                if(i == 1) dp[i] = 2;//数字串开始不是10或者20的情况，dp[1]=2
                else dp[i] = dp[i-1] + dp[i-2];
            }
            else
            {
                dp[i] = dp[i-1];
            }
        }
        
        return dp[len-1];
    }
};

复杂度分析

  • 时间复杂度:  单层遍历，因此时间复杂度为$O(n)$
  • 空间复杂度：使用了一个辅助数组$dp[len]$，因此空间复杂度为$O(n)$

方法二：递归

本题也可采用自上而下，从最大的问题开始，逐渐向下求解 ，因此方法二使用递归的方法。

图解+思路分析

任意给定数字串：”11221“

递归，遍历数字的位，当前位翻译一种方法，如果当前位和下一位能结合成另一种翻译，则又可记录为一种方法。即存在每次只翻译一位数字和每次翻译两位数字的情况，将两者相加进行递归，当字符为0的时候，0没对应的解码，所以直接返回0 (此路解码废掉)，如果当前字符等于1 或者 当前字符加上下一个字符合起来小于等于26 则可以一次解码两个字符。递归结束的条件为找到找到数字串的最后一位。在图中自上问下，从大的问题出发，每次将当前位作为一种翻译方法，如果当前位和下一位能结合则形成另一种翻译方法，以此递归。

JAVA核心代码 

import java.util.*;

public class Solution {
    public int solve (String nums) {
        return back(nums.toCharArray(), 0);
    }
    // 递归函数
    public int back(char[] nums, int start){
        //当start走到终点时，证明已经翻译完毕，直接返回1
        if(start == nums.length){
            return 1;
        }    
        //当字符为0的时候，0没对应的翻译，所以直接返回0 (此路翻译废掉)
        if(nums[start] == '0')
            return 0;
        //每次翻译一个字符
        int res1 = back(nums,start+1);
        int res2 = 0;

        //如果当前字符等于1 或者 当前字符加上下一个字符合起来小于等于26 则可以一次翻译两个字符
        if((start < nums.length-1) && (nums[start] == '1' || (nums[start] == '2' &&nums[start+1] <= '6'))){
            res2 = back(nums,start+2);
        }
        //返回结果
        return res1 + res2;
    }
}

复杂度分析

  • 时间复杂度：递归的时间复杂度为递归的总次数*每次递归的数量，与动态规划的方法比较，有很多子问题被多次计算，因此时间更复杂，时间复杂度为
  • 空间复杂度：空间复杂度为递归的深度*每次递归创建变量的个数，因此空间复杂度为$O(n)$