面试题46: 把数字翻译成字符串

题目

给定一个数字，按照如下规则把它翻译为字符串:0翻译成"a"，1翻译成“b”,.....，11翻译成"l",......,25翻译成"z"。一个数字可能有多个翻译。例如:12258有5种不同的翻译，分别是"bccfi"、"bwfi"、“dczi”、“mcfi” 和“mzi”。编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

解题思路

1. 从最小的子问题开始自下而上解决问题，从而消除重复的子问题。即从数字的末尾开始，然后从右往左翻译并计算不同翻译的数目。
2. 将第i位和第i+1位两位数字拼接起来的数字在10~25的范围内的，翻译次数增加。但此时应注意i应该在 0~length-2的范围内，不然就会出现重复子问题。
3. 若最后两位拼接之后值在10~25的范围内，则count+1。其他情况count += counts[i+2]，因为其他情况时，后一位元素用来拼接，只能找后一个元素对应的上一次元素时的翻译次数。并在此基础上增加。换句话说就是中间元素复用两次。比如:counts[4]=1,count[3]=1此时coverted=58;counts[2]=2,此时coverted=25。也就是计算counts[2]的时候不能考虑count[3]这种情况(复用5)。

代码

class Solution
{
    public:
        int GetTranslationCount(const string& number)
        {
            int length = number.length();//字符串长度
            int* counts= new int[length];//开辟长度为5的内存空间
            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)
                    {
                        if(i < length-2)
                        {
                            count += counts[i+2];
                        }
                        else
                        {
                            count += 1;
                        }
                        cout << "第" << i << "轮count的值: " << count << endl;
                        cout << "digit1:" << digit1 << " digit2:" << digit2 << " converted:" << converted << endl;
                    }
                }
                counts[i] = count;
            }
            count = counts[0];
            delete[] counts;
            return count;
        }

         int GetTranslationCount(int num)
         {
             if(num < 0)
             {
                 return 0;
             }
             string numInString = to_string(num);
             return GetTranslationCount(numInString);
         }
};

完整代码见GitHub