思路：

题目的主要信息：

• 字母到数字分别为1-26映射，没有0
• 输入的数字是字符串，故非常大，超过了long long的表示范围
• 但凡出现11-19，21-26的就可能出现两种译码结果
• 求总后的译码结果种类

方法一：递归（超时）

具体做法：

遍历字符串，每到一位，可以查看它是可以跨越两步还是只能跨越一步，只有11-26（除20外）之间才有两种情况，由此分为两种情况再对之后的字符进行判断，因此可以用递归，每一位为一个子问题。

class Solution {
public:
    int backtrack(string& s, int idx){  //inx记录当前字符的位数
        int n = s.size();
        if(idx == n)  
            return 1;
        if(idx == n - 1 || s.substr(idx, 2) > "26")  //当idx在倒数第二位或者连着两位大于26，只有一种情况
            return backtrack(s, idx + 1);
        return backtrack(s, idx + 1) + backtrack(s, idx + 2);   //有跳1位的，也有跳2位的情况
    }
    int solve(string nums) {
        if(nums == "0")  //排除0
            return 0;
        if(nums == "10" || nums == "20")  //排除只有一种可能的10 和 20
            return 1;
        for(int i = 1; i < nums.length(); i++){  //当0的前面不是1或2时，无法译码，0种
            if(nums[i] == '0')
                if(nums[i - 1] != '1' && nums[i - 1] != '2') 
                    return 0;
        }
        return backtrack(nums, 0);
    }
};

复杂度分析：

• 时间复杂度：$O\left(2^n\right)O(2^n)$O(2n)，这是一个树形递归，故为$O\left(2^n\right)O(2^n)$O(2n)
• 空间复杂度：$O\left(n\right)O(n)$O(n)，递归树深度

方法二：动态规划

具体做法：

用辅助数组dp表示前i个数的译码方法有多少种。对于一个数，我们可以直接译码它，也可以将其与前面的1或者2组合起来译码。

• 如果直接译码，则$dp\left[i\right]=dp[i-1]dp[i]=dp[i-1]$dp[i]=dp[i−1]
• 如果组合译码，则$dp\left[i\right]=dp[i-2]dp[i]=dp[i-2]$dp[i]=dp[i−2]

对于只有一种译码方式的，选上种$dp[i-1]dp[i-1]$dp[i−1]即可，对于满足两种译码方式（10，20不能）则是$dp[i-1]+dp[i-2]dp[i-1]+dp[i-2]$dp[i−1]+dp[i−2] 依次相加，最后的$dp\left[length\right]dp[length]$dp[length]即为所求答案。

class Solution {
public:
    int solve(string nums) {
        if(nums == "0")  //排除0
            return 0;
        if(nums == "10" || nums == "20")  //排除只有一种可能的10 和 20
            return 1;
        for(int i = 1; i < nums.length(); i++){  //当0的前面不是1或2时，无法译码，0种
            if(nums[i] == '0')
                if(nums[i - 1] != '1' && nums[i - 1] != '2')
                    return 0;
        }
        vector<int> dp(nums.length() + 1, 1);  //辅助数组初始化为1
        for(int i = 2; i <= nums.length(); i++){
            //在11-19，21-26之间的情况
            if((nums[i - 2] == '1' && nums[i - 1] != '0') || (nums[i - 2] == '2' && nums[i - 1] > '0' && nums[i - 1] < '7'))
               dp[i] = dp[i - 1] + dp[i - 2];
            else
                dp[i] = dp[i - 1];
        }
        return dp[nums.length()];
    }
};

复杂度分析：

• 时间复杂度：$O\left(n\right)O(n)$O(n)，两次遍历都是单层
• 空间复杂度：$O\left(n\right)O(n)$O(n)，辅助数组dp