剑指46：把数字翻译成字符串

传送门

nowcoder
leetcode

题目描述

有一种将字母编码成数字的方式：’a’->1, ‘b->2’, … , ‘z->26’。
给一串数字，返回有多少种可能的译码结果。
数据范围：字符串长度满足 0 < n < 90
要求：时间复杂度 O(n)，空间复杂度 O(n)

C++ 代码 - nowcoder

/*
    状态表示：
        f[i] 表示以第 i 位结尾的前缀串译码的方案数
    状态计算：
        f[i] = f[i - 1] + f[i - 2] (条件：i − 1 >= 0, 10 <= x <= 25)
        1.单独翻译对 f[i] 的贡献为 f[i - 1]；
        2.如果第 i - 1位存在，且第 i - 1 位和第 i 位形成的数字 x 满足 10 <= x <= 25，
            那么把第 i - 1 位和第 i 位连起来翻译，对 f[i] 的贡献为 f[i - 2]，否则为 0。
    初始化：
        f[0] = 1, f[1] = 1
    遍历顺序：
        从前向后
*/
class Solution {
public:
    int solve(string nums) {
        if (nums.empty() || nums[0] == '0') return 0;

        int n = nums.size();
        vector<int> f(n + 1);
        f[0] = 1, f[1] = 1;
        for (int i = 2; i <= n; i ++) {
            if (nums[i - 1] == '0') {
                if (nums[i - 2] == '1' || nums[i - 2] == '2') f[i] = f[i - 2];
                else f[i] = 0;
            } else if (nums[i - 2] == '1' || (nums[i - 2] == '2' && nums[i - 1] <= '6')) {
                f[i] = f[i - 2] + f[i - 1];
            } else {
                f[i] = f[i - 1];
            }
        }

        return f[n];
    }
};

C++ 代码 - leetcode

/*
    状态表示：
        f[i] 表示以第 i 位结尾的前缀串译码的方案数
    状态计算：
        f[i] = f[i - 1] + f[i - 2] (条件：i − 1 >= 0, 10 <= x <= 25)
        1.单独翻译对 f[i] 的贡献为 f[i - 1]；
        2.如果第 i - 1位存在，且第 i - 1 位和第 i 位形成的数字 x 满足 10 <= x <= 25，
            那么把第 i - 1 位和第 i 位连起来翻译，对 f[i] 的贡献为 f[i - 2]，否则为 0。
    初始化：
        f[0] = 1, f[1] = 1
    遍历顺序：
        从前向后
*/
class Solution {
public:
    int crackNumber(int num) {
        string s = to_string(num);
        int n = s.size();
        if (n < 1) return 0;

        // 定义：f[i] 表示 s[0..i-1] 解码方式数量
        vector<int> f(n + 1);
        // base case: s 为空或者 s 只有一个字符
        f[0] = 1, f[1] = 1;
        for (int i = 2; i <= n; i++) {
            if (s[i - 1] >= '0' && s[i - 1] <= '9') {
                // s[i] 本身作为一个字母
                f[i] += f[i - 1];
            }
            if (s[i - 2] == '1' || s[i - 2] == '2' && s[i - 1] <= '5') {
                // s[i] 和 s[i - 1] 合起来表示一个字母
                f[i] += f[i - 2];
            }
        }

        return f[n];
    }
};