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

Tags: Depth-first Search

Links: https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof/

---

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

示例 1:

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

提示：

• 0 <= num < $2^{31}$

---

class Solution {
    int cnt;
    string number;
    int n;
public:
    int translateNum(int num) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        cnt = 0;
        number = to_string(num);
        n = number.size();
        DFS(0);

        return cnt;
    }

    void DFS(int pos) {
        for (int len = 1; len <= 2; ++len) {
            if (pos + len - 1 < n && stoi(number.substr(pos, len)) <= 25) {
                if (len == 2 && number.substr(pos, len)[0] - '0' == 0) continue;

                if (pos + len - 1 == n - 1) {
                    ++cnt;
                }
                else DFS(pos + len);
            }
        }
    }
};

属于搜索框架的第一种，注意如果不加上22行的代码，会在506这个样例错误，也就是06不能按照6来计算，所以需要去掉两位数中0开头的数字。