Leetcode题解剑指 Offer 46. 把数字翻译成字符串

PROBLEM

难度中等

MY ANSWER

将数字转换为字符串，使用动态规划。时间复杂度O(logn)，空间复杂度O(logn)。代码还可继续优化：因为只需用到i - 2和i - 1的结果，所以可以不使用数组存储每位的结果，只使用两个变量储存前两位的结果。

class Solution {
public:
    int translateNum(int num) {
        vector<int> res;
        res.push_back(1);
        res.push_back(1);
        string str = to_string(num);
        for(int i = 1; i < str.size(); i++) {
            int tmp = res[i];
            if(str.substr(i - 1, 2) <= "25" && str.substr(i - 1, 2) >= "10") {
                tmp += res[i - 1];
            }
            res.push_back(tmp);
        }
        return res[res.size() - 1];
    }
};

BETTER SOLUTION

使用求余和求整实现从右向左的遍历进行动态规划，将空间复杂度降到常数。从右向左和从左向右的动态规划结果相同。

迭代

class Solution {
    public:
    int translateNum(int num) {
        int a = 1, b = 1, x, y = num % 10;
        while(num != 0) {
            num /= 10;
            x = num % 10;
            int tmp = 10 * x + y;
            int c = (tmp >= 10 && tmp <= 25) ? a + b : a;
            b = a;
            a = c;
            y = x;
        }
        return a;
    }
};

递归

class Solution {
public:
    int translateNum(int num) {
        if (num<=9) {return 1;}
        //获取输入数字的余数，然后递归的计算翻译方法
        int ba = num%100;
        //如果小于等于9或者大于等于26的时候，余数不能按照2位数字组合，比如56，只能拆分为5和6；反例25，可以拆分为2和5，也可以作为25一个整体进行翻译。
        if (ba<=9||ba>=26) {return translateNum(num/10);}
        // ba=[10, 25]时，既可以当做一个字母，也可以当做两个字母
        else  {return translateNum(num/10)+translateNum(num/100);}
    }
};

SUMMARY

动态规划时还可注意如何降低空间复杂度。