剑指 Offer 46 把数字翻译成字符串

概述

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

遍历 + 缓存

O(n) 时间复杂度，O(n) 空间复杂度。

class Solution {
public:
    string num;
    vector<int> cache;
    int translateNum(int num) {
        this->num = to_string(num);
        cache.resize(this->num.size(), -1);
        return helper(0);
    }

    int helper(int i) {
        if (i == num.size()) return 1;
        if (i == num.size() + 1) return 0;
        if (cache[i] != -1) return cache[i];
        if (num[i] == '1') {
            cache[i] = helper(i+1) + helper(i+2);
        } else if (num[i] == '2') {
            cache[i] = helper(i+1);
            if (i + 1 < num.size() && num[i+1] <= '5') {
                cache[i] += helper(i+2);
            }
        } else {
            cache[i] = helper(i+1);
        }
        return cache[i];
    }
};