一、题目描述

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

二、算法1（暴力深搜）

解题思路

  1. 暴力枚举每一种翻译方式，最后统计方案数
  2. 每次递归考虑两种情况，当前位的数自成一位与下一位数结合，当然，考虑只有当前一位时不能为0，考虑两位数时数值应该是10到26的范围
    图片说明

代码实现（C++11）

class Solution {
public:
    int solve(string nums) {
        int n = nums.size();
        return dfs(nums, 0, n);
    }

    int dfs(string& nums, int p, int n) {
        if (p == n) return 1;    // 找到一种合法结果

        int ans = 0;
        // 若当前位不为'0', 自成一类
        if (nums[p] != '0') ans += dfs(nums, p + 1, n);

        // 考虑当前位和下一位结合为一类
        if (p + 1 < n) {
            int digit = (nums[p] - '0') * 10 + (nums[p + 1] - '0');
            if (digit >= 10 && digit <= 26) ans += dfs(nums, p + 2, n);
        }

        return ans;
    }
};

时间复杂度：, n为给定字符串的长度，最坏情况下每次分两条路递归，时间复杂度指数级
空间复杂度：，递归深度为字符串长度n

优化（记忆化搜索）

暴力搜索的时间复杂度高在存在很多重复的分支，因此我们可以使用记忆化搜索，记录已知状态的结果，当重复某一已知步骤时，直接从备忘数组memo中取出结果返回即可，这里memo定义为从当前遍历到的位置到结尾的合法结果数

class Solution {
public:
    int solve(string nums) {
        int n = nums.size();
        vector<int> memo(n, -1);    // memo[i]表示从当前位置到结尾的合法方案数
        dfs(nums, 0, n, memo);
        return memo[0];
    }

    int dfs(string& nums, int p, int n, vector<int>& memo) {
        if (p == n) return 1;    // 找到一种合法结果
        if (memo[p] != -1) return memo[p];

        int ans = 0;
        // 若当前位不为'0', 自成一类
        if (nums[p] != '0') ans += dfs(nums, p + 1, n, memo);

        // 考虑当前位和下一位结合为一类
        if (p + 1 < n) {
            int digit = (nums[p] - '0') * 10 + (nums[p + 1] - '0');
            if (digit >= 10 && digit <= 26) ans += dfs(nums, p + 2, n, memo);
        }

        return memo[p] = ans;
    }
};

时间复杂度：, n是字符串长度，时间复杂度为dp相近
空间复杂度：, 递归栈空间和备忘数组占用空间

三、算法2（动态规划）

解题思路

  1. 求方案数问题一般都涉及到动态规划，要得到整个数字的翻译结果，可以从更小规模的数字推出，因此可以联想到线性动规
  2. 定义数组f[i]表示数字nums[0...i]能被翻译成多少种结果，对于当前字符nums[i]，最多只有两种情况，若能自成一位，则方案数为f[i - 1]，若能和前面一位结合成合法的两位数，则方案数为f[i - 2]，若两种都满足则方案数为f[i - 1] + f[i - 2]
    故状态转移方程为：

    其中B表示nums[i]表示的数, AB表示nums[i - 1]和nums[i]组合的数

代码实现（C++11）

class Solution {
public:
    int solve(string nums) {
        int n = nums.size();
        vector<int> f(n + 1);
        // 预处理f[0]和f[1], 可以避免边界处理
        f[0] = 1, f[1] = nums[0] != '0';

        for(int i = 2; i <= n; i++) {
            if(nums[i - 1] != '0') f[i] = f[i - 1];    // 若当前位不为'0'，可单独翻译
            int digit = (nums[i - 2] - '0') * 10 + (nums[i - 1] - '0');
            if (10 <= digit && digit <= 26) {    // 当前位与上一位数组合（必须是合法的两位数字）
                f[i] += f[i - 2];
            }
        }
        return f[n];
    }
};

时间复杂度：, n为字符串长度，遍历一次数组，时间复杂度为O(n)
空间复杂度：, 辅助数组使用的空间是O(n)的