BM69. [把数字翻译成字符串]

alt

https://www.nowcoder.com/exam/oj?tab=%E7%AE%97%E6%B3%95%E7%AF%87&topicId=295

BM69. 把数字翻译成字符串

https://www.nowcoder.com/practice/046a55e6cd274cffb88fc32dba695668?tpId=295&sfm=discuss&channel=nowcoder

题目的主要信息：

字母到数字分别为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(2^n)$ ，这是一个树形递归，故为 $O(2^n)$
空间复杂度： $O(n)$ ，递归树深度

方法二：动态规划

具体做法：

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

如果直接译码，则 $dp[i]=dp[i-1]$
如果组合译码，则 $dp[i]=dp[i-2]$

对于只有一种译码方式的，选上种 $dp[i-1]$ 即可，对于满足两种译码方式（10，20不能）则是 $dp[i-1]+dp[i-2]$
依次相加，最后的 $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()];
    }
};

复杂度分析：