题目描述

• 给定一个数字，我们按照如下规则把它翻译为字符串： 0翻译成 'a'，1 翻译成 'b'， ......，11 翻译成 'l'，25 翻译成 'z'
• 一个数字可能有多个翻译
• 例如， 12258 有 5 种不同的翻译，分别是 'bccfi'，'bwfi'，'bczi'，'mcfi'，'mzi'
• 请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法

题目解读

• 剑指Offer 231

代码

#include<iostream>
using namespace std;

class Solution {
public:
    int Core(const string& number){
        int length = number.length();
        int *counts = new int[length]; // 记录从字符串的每个位置开始翻译的翻译种树
        int count = 0;

        for (int i = length-1; i >= 0; i--) // 自底向上，避免求解重复子问题
        {
            count = 0;
            if (i < length-1){
                count = counts[i+1];
            }
            else{ // 从末尾开始翻译只有一种
                count = 1;
            }

            if(i < length-1){
                int digit1 = number[i] - '0';
                int digit2 = number[i+1] - '0';
                int converted = digit1*10 + digit2;
                if (converted >= 10 && converted <= 25) // 判断i和i+1位置上的整数拼接是否满足翻译的要求
                {
                    if(i < length-2){ 
                        count += counts[i+2]; // 满足要求时，从 i 位置开始翻译的种树还包括从 i+2 开始翻译的种树
                    }
                    else{
                        count += 1; // 从倒数第二个数开始翻译，
                    }
                }
            }

            counts[i] = count;
        }

        count = counts[0];
        delete[] counts;

        return count;
    }

    int getTranslationCount(int number){
        if(number < 0){
            return 0;
        }

        return Core(to_string(number));
    }
};

int main(){
    Solution ss;
    cout<<ss.getTranslationCount(12258)<<endl;
}

总结展望

• 要和青蛙跳台阶一块分析分析啊..