面试题46

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

示例 1:

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

提示：

• 0 <= num < 231

Solutions

1. dfs

class Solution {
public:
    int transnum(const string & s, int st) {
        if (st > s.size())
            return 0;
        if (st == s.size())
            return 1;
        int res = 0;
        res += transnum(s, st + 1);
        if (s[st] != '0' && stoi(s.substr(st, 2)) <= 25)
            res += transnum(s, st + 2);

        return res;
    }

    int translateNum(int num) {
        return transnum(to_string(num), 0);
    }
};

1. recursion with memoization

class Solution {
public:
    vector<int> memo;
    int solve(string & s, int st) {
        if (st < 0)
            return 0;
        if (memo[st] != -1)
            return memo[st];
        memo[st] = 0;
        memo[st] += solve(s, st - 1);
        if (st - 2 >= 0 && s[st - 2] != '0' && stoi(s.substr(st - 2, 2)) <= 25)
            memo[st] += solve(s, st - 2);

        return memo[st];

    }
    int translateNum(int num) {
        string s = to_string(num);
        memo = vector<int>(s.size() + 1, -1);
        memo[0] = 1;
        return solve(s, s.size());
    }
};

1. dynamic programming

class Solution {
public:
    int translateNum(int num) {
        string s = to_string(num);
        vector<int> dp(s.size() + 1);

        dp[0] = 1;
        for (int i = 1; i < dp.size(); i++) {
            dp[i] += dp[i - 1];
            if (i >= 2 && s[i - 2] != '0' && stoi(s.substr(i - 2, 2)) <= 25)
                dp[i] += dp[i - 2];
        }

        return dp[s.size()];
    }
};

Or

class Solution {
public:
    int translateNum(int num) {
        string s = to_string(num);
        int pprev = 0, prev = 1;


        for (int i = 1; i < s.size() + 1; i++) {
            int cur = 0;
            cur += prev;
            if (i >= 2 && s[i - 2] != '0' && stoi(s.substr(i - 2, 2)) <= 25)
                cur += pprev;
            pprev = prev;
            prev = cur;
        }

        return prev;
    }
};