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

题目描述

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

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

提示：
0 <= num < 231

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

解题思路

先以题目给的用例12258为例，找翻译方法数量的规律。

# 1的翻译方法：1
# 1 2的翻译方法（1 2）（12）
# 1 2 2的翻译方法（1 2 2）（12 2）（1 22）
# 1 2 2 5的翻译方法（1 2 2 5）（12 2 5）（1 22 5）（1 2 25）（12 25）
# 1 2 2 5 8的翻译方法（1 2 2 5 8）（12 2 5 8）（1 22 5 8）（1 2 25 8）（12 25 8）

先用str(num)把数转换为字符串，随后针对字符串，使用动态规划。
状态定义：
dp[i]为遍历到第i个数时，总共的翻译方法。
初始状态：
dp[0] = [1]。
dp[1]根据能否和str_num[0]组成一个新字母，而为1或者2。
转移方程：
如果 str_num[i]可以和str_num[i-1]组成一个新字母，则dp[i] = dp[i-1] + dp[i-2]。
否则 dp[i] = dp[i-1]。
返回值：dp[-1]。

解题代码

class Solution:
    def translateNum(self, num: int) -> int:
        # 1的翻译方法：1
        # 1 2的翻译方法（1 2）（12）
        # 1 2 2的翻译方法（1 2 2）（12 2）（1 22）
        # 1 2 2 5的翻译方法（1 2 2 5）（12 2 5）（1 22 5）（1 2 25）（12 25）
        # 1 2 2 5 8的翻译方法（1 2 2 5 8）（12 2 5 8）（1 22 5 8）（1 2 25 8）（12 25 8）
        num_str = str(num)
        num_str_length = len(num_str)
        # dp[i]为遍历到i时，总共的翻译方法
        dp = [0] * len(num_str)
        dp[0] = 1
        if num_str_length >= 2:
            if int(num_str[0]) == 1 or (int(num_str[0]) == 2 and int(num_str[1]) <= 5):
                dp[1] = 2
            else:
                dp[1] = 1
            for i in range(2, len(num_str)):
                if int(num_str[i-1]) == 1 or (int(num_str[i-1]) == 2 and int(num_str[i]) <= 5):
                    dp[i] = dp[i-1] + dp[i-2]
                else:
                    dp[i] = dp[i-1]
        return dp[-1]

执行结果

执行结果：通过
执行用时：32 ms, 在所有 Python3 提交中击败了62.18%的用户
内存消耗：14.9 MB, 在所有 Python3 提交中击败了57.57%的用户