题解 | #未排序数组中累加和为给定值的最长子数组长度#

把数字翻译成字符串

http://www.nowcoder.com/practice/046a55e6cd274cffb88fc32dba695668

方法一：动态规划

1.解题思路

题意：
对与给定的一串数字，按照a与1映射，b与2映射，......，z与26映射的方式，将该串数字翻译为字符串，问总共有多少种翻译方式。
分析：
因为对于a~ z，分别用1~ 26来表示。要注意0不能单独存在，0必须依托前面一位数字，且前面一位数字必须为1或2。此处需要进行特判，不满足条件直接返回0。综上可以将1~26分成两类。

要么取一个字符的子串翻译，要么取两个字符的子串翻译。

只能表示1种翻译方式：1~10,20。这些数字无法拆分。
可以表示2~ 3种翻译方式：11~ 19,21~26。这些数字可以拆分，如19可拆分为1,9,19的子串

2.解法

设dp数组， $dp[i]$ 表示前i个数的译码方法。
初始化dp,当串没有元素或只有1个元素时，只能有一种翻译方式。接着我们不断取长度为2的子串，判断可否拆分。

对不可拆分的子串， $dp[i]=dp[i-1]$ ;
对可以拆分的子串， $dp[i]=dp[i-1]+dp[i-2]$ ;

最后 $dp[字符串长度]$ 即为该串的翻译方法数

3.具体代码

class Solution {
public:
    int solve(string nums) {
        // write code here
        if(nums=="0")return 0; 
        int len=nums.size();//字符串长度 
        for(int i=1;i<len;i++){//遍历字符串
            if(nums[i]=='0'&&(nums[i-1]!='1'&&nums[i-1]!='2')){//因为0必须搭配前面一个数字，如果前面的值不为1或2，说明该串违规，直接返回
                return 0;
            }
        }
        vector<int>dp(nums.size()+1,0);//dp[i]表示前i个数的译码方法 
        dp[0]=dp[1]=1;//初始化
        for(int i=2;i<=len;i++) {//遍历串
            string s=nums.substr(i-2,2);//取2个字符构成的串
            if(s>="11"&&s<="19"||s>="21"&&s<="26")dp[i]=dp[i-1]+dp[i-2];//该串可拆分，有多种编码方式
            else dp[i]=dp[i-1];//该串不可拆分，只有一种编码方式
        }
        return dp[len];
    }
};

4.时间复杂度和空间复杂度分析

时间复杂度： $O(n)$ ，n是字符串长度，只用到了2次遍历字符串
空间复杂度： $O(n)$ ，n是字符串长度，只用到了一个辅助数组dp

方法二：递归（超时）

1.解题思路

由题意易知，要么取一个字符的子串翻译，要么取两个字符的子串翻译，所以建立一颗递归树，向左遍历字符串的增量为1，向右增量为2。

2.解法

首先空串，0前面不是1或2的串，都直接返回，这里预处理同解法一相同。然后采用递归的方式深度优先搜索一下字符串。递归边界为遍历一遍串，接着ans++，记录翻译方法次数。递归中建立一颗递归树，向左为不断取长度为1的子串翻译，向右为不断取长度为2的子串翻译。

3.图解

图片说明

4.具体代码

class Solution {
public:    
    int solve(string nums){
       if(nums=="0")return 0;//同解法一的预处理，空串，0前面不是1或2的串，都直接返回
        for(int i=1;i<nums.size();i++){
            if(nums[i]=='0'&&(nums[i-1]!='1'&&nums[i-1]!='2')){
                return 0;
            }
        }
        int ans=0;//记录翻译方式数
        dfs(nums,0,ans);
        return ans;
    }
    void dfs(string &s,int idx,int &ans){
        if(idx == s.length()){//翻译了一遍
            ans++;//翻译方式数++
            return;
        }
        //递归1个数字
        if(stoi(s.substr(idx,1)) <= 26)dfs(s,idx+1,ans);     
        //递归2个数字
        if(idx < s.length()-1&&stoi(s.substr(idx,2))<=26&&stoi(s.substr(idx,2))>=21||stoi(s.substr(idx,2))<=19&&stoi(s.substr(idx,2))>=11)dfs(s,idx+2,ans);               
    }  
};