题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

class Solution {
public:
    int getTranslationCount(string s) {
        int n = s.size();
        /*
        f[i]表示前i位有多少种翻译方式
        1.把第i位数字单独翻译成一个字母     f[i] = f[i - 1]
        2.把第i位和第i-1位翻译成一个字母，但是需要先判断 (1) i > 1
                                                        （2）10 <= s[i-1]*10 + s[i]+ <= 25
                f[i] = f[i - 2]
        */
        vector<int> f(n + 1);
        f[0] = 1;
        for(int i = 1; i <= n; i++){
            f[i] = f[i - 1]; // 第i个字符单独翻译
            if(i > 1){
                int t = (s[i - 1] - '0') + (s[i - 2] - '0')*10; // s下标是从0开始算
                if(t >= 10 && t <= 25) f[i] += f[i - 2];
            }
        }
        return f[n];
    }
};