玖叶教程网

题目：

给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

示例：

输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"

思路一：

动态规划

把数字转成字符串s

dp[i]表示截止字符串s第i位的不同翻译方法，状态转移公式如下：

dp[i]=dp[i-1]+dp[i-2]), 如果子串s[i-1,i]是合法数字

dp[i]=dp[i-1], 如果子串s[i-1,i]是非法数字

思路二：

递归，尝试每一种可能的翻译，记录下合法翻译的个数。

代码一：

class Solution {
public:
    bool valid(const string substr)
    {
        int val = stoi(substr);
        if(substr.size() == 1 && val >=0 && val <=9)
            return true;
        if(substr.size() == 2 && val >=10 && val <=25)
            return true;
        return false;
    }


    int translateNum(int num) {
        string s=to_string(num);

        int a=1;
        if(s.size() == 1)
            return a;
         
        string ss=s.substr(0, 2);
        int b=valid(ss) ? 2: 1;
        if(s.size() == 2)
            return b;
        
        int c=0;
        for(int i=2; i<s.size(); i++)
        {
            string ss=s.substr(i-1, 2);
            if(valid(ss))
            {
                c=a+b;
            }else
                c=b;
            
            a=b;
            b=c;
        }

        return c;
    }
};

代码二：

class Solution {
public:
    bool valid(string& s, int i, int len)
    {
        int n=s.size();
        int j=i+len-1;
        if(i>=0 && i<n && j>=0 && j<n)
        {
            int val = stoi(s.substr(i, len));
            if(len == 1 && val >=0 && val <=9)
                return true;
            if(len ==2 && val >=10 && val <=25)
                return true;
            return false;
        }else
            return false;
    }

    void handle(string& s, int i, int& count)
    {
        if(i>=s.size())
        {
            count++;
            return;
        }

        vector<int> v={1,2};
        for(auto& len: v)
        {
            if(valid(s, i, len))
            {
                handle(s, i+len, count);
            }
        }

    }

    int translateNum(int num) {
        int count=0;

        string s=to_string(num);
        handle(s, 0, count);

        return count;
    }
};