AcWing 59. 把数字翻译成字符串

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 59. 把数字翻译成字符串原题链接中等

作者：

贺谦 , 2020-05-08 23:52:46 , 所有人可见 , 阅读 1557

题目描述

给定一个数字，我们按照如下规则把它翻译为字符串：

0翻译成”a”，1翻译成”b”，……，11翻译成”l”，……，25翻译成”z”。

一个数字可能有多个翻译。例如12258有5种不同的翻译，它们分别是”bccfi”、”bwfi”、”bczi”、”mcfi”和”mzi”。

请编程实现一个函数用来计算一个数字有多少种不同的翻译方法。

样例

输入："12258"

输出：5

算法

(DP)

这道题看的题解，不是很理解。似懂非懂，希望大佬看到了给个提示。
为什么将第i个数字单独翻译成字母，方案数是f[i - 1]？
如果将第i - 1和第i个数字一起翻译成字母，方案数是f[i - 2]？

时间复杂度

$O(n)$

C++ 代码

class Solution {
public:
    int getTranslationCount(string s) {
        int n = s.size();
        vector<int> f(n + 1, 0);
        f[0] = 1;
        for(int i = 1; i <= n; i ++)
        {
            f[i] = f[i - 1];
            int t = (s[i - 2] - '0') * 10 + s[i - 1] - '0';
            if(t >= 10 && t <= 25) f[i] += f[i - 2];
        }

        return f[n];
    }
};

8 评论

马里奥 2020-06-20 16:22

i-2 i=1时不越界？

初静 2021-05-25 23:24

class Solution {
public:
    int getTranslationCount(string s) {
        int n = s.size();  // 12345
        int f[n + 1];
        f[0] = 1;
        f[1] = 1;
        for (int i = 2; i <= n; i ++) {
            f[i] = f[i - 1];
            int w = (s[i - 2] - '0') * 10 + s[i - 1] - '0';
            if (i >= 1 && w >= 10 && w <= 25) f[i] += f[i - 2];
        }
        return f[n];
    }
};

wzc1995 2020-05-09 00:04

想想状态定义

贺谦 2020-05-09 00:19

f[i]表示前i位数字一共有多少种不同的解析方法。
如果第i位数字单独解析，它是不影响前i - 1个数字的解析方法的，所以就顺带的事儿。我之前疑惑的是为什么不是f[i] = f[i - 1] + 1。
同理，如果第i - 1和第i位数字一起解析的话，就是前i - 2位数字的解析方法数不受影响了，所以是f[i - 2]。