剑指offer 47. 把数字翻译成字符串

✍个人博客:https://blog.csdn.net/Newin2020?spm=1011.2415.3001.5343
专栏地址:剑指offer系列题解
原题地址:题目地址
专栏定位:为找工作的小伙伴整理常考算法题解,祝大家都能成功上岸!
❤️如果有收获的话,欢迎点赞收藏,您的支持就是我创作的最大动力

题目描述

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

0 翻译成 a,1 翻译成 b,……,11 翻译成 l,……,25 翻译成 z

一个数字可能有多个翻译。

例如 12258 有 5 种不同的翻译,它们分别是 bccfibwfibczimcfimzi

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

数据范围

输入数字位数 [1,101]。

样例

输入:"12258"

输出:5

方法一:动态规划 O(n)

状态表示:f[i] 表示将前 i 位数字翻译成字符串的方案数。

状态计算:

  • f[i] = f[i-1] ,当前位的数字只算一位是一定能构成合法方案的。
  • 只有当当前位的数字和它前面的那一位能构成 10 ~ 25 之间的数字时,f[i] += f[i-2]

可以发现这个思路和递推的思想很类似,由两个方向可以递推过来,我们举一个例子,假如当前已经遍历到 142 ,第三位是 2 ,它可以由前面一位的方案转移过来即 f[i] = f[i-1] 。但是发现 42 并不在 10 ~ 25 的范围内,所以不能转换成字母,所以就不用从前两位的方案转移过来。

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

欢迎大家在评论区交流~

你可能感兴趣的