jz046.把数字翻译成字符串

题目链接

我们以12258为例分析如何从数字的第一位开始一步步计算不同的翻译方法的数目，我们有两种不同的选择来翻译第一位数字1。第一种选择是数字1单独翻译成“b”，后面剩下数字2258；第二种选择是1和紧挨着的2一起翻译成“m“，后面剩下数字258。当最开始的一个或者两个数字被翻译成一个字符后，我们接着翻译后面剩下的数字。显然我们可以用递归函数来计算翻译的数目。

我们定义函数f（i）表示从第i位数字开始的不同翻译的数目，那么f（i）= f（i+1）+ g（i，i+1）x f（i+1），当第i为和第i+1位两位数字拼接起来的数字在10-25的范围内时，函数g（i， i+1）的值为1；否则为0。

尽管我们用递归的思路来分析这个问题，但由于存在重复的子问题，递归并不是解决这个问题的最佳方法。还是以12258为例，如前所述，翻译12258可以分解成两个问题：翻译1和2258，以及翻译12和258。接下来我们翻译第一个子问题中剩下的2258，同样也可以分解成两个子问题：翻译2和258，以及翻译22和58.注意到子问题翻译258重复出现了。递归从最大的问题开始自上而下解决问题，我们也可以从最小的子问题开始自下而上解决问题，这样就可以消除重复的子问题。也就是说，我们从数字的末尾开始，如何从右到左翻译并计算不同翻译的数目。代码如下所示，这个算法的时间复杂度是O（N），空间复杂度由于要存string类型的num所以仍是O（N）。下面，我们用取模和取余运算，减少了存储num的string的多余内存。

class Solution:
    def translateNum1(self, num: int) -> int:
        s = str(num)
        a = b = 1
        for i in range(2, len(s) + 1):
            a, b = (a + b if "10" <= s[i - 2:i] <= "25" else a), a
        return a

    def translateNum2(self, num: int) -> int:
        a = b = 1
        y = num % 10
        while num != 0:
            num //= 10
            x = num % 10
            a, b = (a + b if 10 <= 10 * x + y <= 25 else a), a
            y = x
        return a