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

2020-06-09 本文已影响0人大梦三千秋

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

题目来源：力扣（LeetCode）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 < 231

解题思路

思路：动态规划

先理清题意，题目中说明规则： 0 翻译成 "a"， 1 翻译成 "b"，...，25 翻译成 "z"。而且题目中也说明【一个数字可能有多个翻译】。那么这里就可以想到，当数字大于等于 10 小于等于 25 的时候，这部分的数字可以看出是两个单独数字组成，或者单独当成一个数字。

现在看示例 1：

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

看下面的解释中，我们可以看到：

"bccfi" 这种情况就是将所有的数字单独翻译，即是 [1, 2 ,2, 5, 8]
剩下的 4 个就是连续两位数字可考虑组合的情况
- [1, 22, 5, 8] 对应翻译的是 "bwfi"
- [1, 2, 25, 8] 对应翻译的是 "bczi"
- [12, 2, 5, 8] 对应翻译的是 "mcfi"
- [12, 25, 8] 对应翻译的是 "mzi"

在上面的示例中，'58' 这个组合是不成立的，我们知道组合的数字的范围应该落在 [10, 25] 之间。

那么也就是说，翻译的规则，在字符串的第 i 个位置中可以分为两种情况：

单独进行翻译
如果与 i - 1 位能够组合成数字且落在 [10, 25]，那么可以连起来翻译。

现在假设将题目给出的数字 num 第 i 个数字记为 $x_i$ ，例如示例中的 num = 12258，那么 $x_1$ 就是 1。

现在定义动态规划列表 dp，假设 dp[i] 为 $x_i$ 结尾的数字的翻译方案。

按照前面得出的翻译规则总结出转移方程。

当 $x_{i-1}$ 和 $x_i$ 两个数字组合可被翻译时，这里就会有两种情况。单独翻译，或者组合翻译。也就是：

当组合翻译的时候， $x_{i-1}x_i$ 组合确定，前面 i-2 个数的翻译方案为 dp[i-2]。
当单独翻译的时候， $x_i$ 确定，前面 i-1 个数的翻译方案为 dp[i-1]。
也就是说当 $x_{i-1}$ 和 $x_i$ 两个数字组合可被翻译的时候，可由上述两种情况结合，最终 dp[i] = dp[i-2] + dp[i-1]。

如果 $x_{i-1}$ 和 $x_i$ 两个数字无法组合，那么就只能当成单个数字进行翻译。所以 dp[i] = dp[i-1]。

这里需要注意的可组合数字落在的区间是 [10, 25]，前面已经说明了，只有这种情况才能够成功组合被翻译。

还有一种情况，就是 $x_{i-1}$ 为 0 的时候，这种情况可以会出现 00, 01, 02, ... 这样的组合数字。但是这种情况是不能够被翻译的。

所以最终的状态转移方程，以及具体落在的区间：

$dp[i] = \begin{cases} dp[i-2] + dp[i-1]， & 10x_{i-1} + x_i \in [10, 25] \\ dp[i-1] & 10x_{i-1} + x_i \in [0, 10) \bigcup (25, 99] \end{cases}$

注意，这里我们并不考虑三位数的组合

在这里，dp[i] 表示的是以 $x_i$ 结尾的数字的翻译方案。当 i=0 和 i=1 的时候，表示的是【无数字】和【第一个数字】。这里都初始化为 1。（前面说明了 $x_1$ 表示的是第 1 个数字，如题目 12258 中的第一个数字 1。）

反向推导 dp[0] 的值，假设当出现两个数字能够组合且被翻译的情况下，例如 12，那么 dp[2] 显然是等于 2。要么以 [1, 2] 的形式，要么以 [12] 的形式进行翻译。
此时 dp[2] = dp[1] + dp[0] = 2，而 dp[1] 为 1，那么 dp[0] = 1。

而最终我们需要求得的结果就是 dp[n]，也就是题目中所需求的翻译方案（n 表示的是数字长度。）

在这里可以使用字符串截取的方法去实现，这里需要将数字下转换为字符串，缺点是字符串会占用一定的空间。这里采用字符串截取的方法来求解。还有一种方法是使用取模的方法（可考虑尝试）

具体的代码如下。

代码实现

class Solution:
    def translateNum(self, num: int) -> int:
        string = str(num)
        n = len(string)

        dp = [0] * (n+1)
        
        dp[0]=1
        dp[1]=1

        for i in range(2, n + 1):
            if "10" <= string[i-2:i] <="25":
                dp[i] = dp[i-1] + dp[i-2]
            else:
                dp[i] = dp[i-1]
        
        return dp[n]

实现结果

总结

本题使用的动态规划，先分析题意，找出翻译的规则。可以发现，当第 i 个数字被翻译的时候，可能出现两种情况：
- 单独翻译第 i 个位置的数字
- 当第 i 个位置的数字与第 i-1 位置的数字组合且可被翻译，那么可考虑组合进行翻译
根据上面的翻译规则，可以求得转移方程(具体参考上面的解析)：
- 当两个连续数字能够组合的情况下：dp[i] = dp[i-2]+dp[i-1]
- 否则：dp[i]=dp[i-1]
对动态规划列表进行初始化，确定最终求解的值为 dp[n]。

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

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

题目

解题思路

代码实现

实现结果

总结

猜你喜欢

热点阅读