lucifer

原题地址: 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

思路

我们另 f(n)表示给定数字 num 的情况下,从 num 的第 1 位(包含)到第 n 位(包含)有多少种不同的翻译方法。

我们从几个简单的例子入手,尝试打开思路。

对于数字 12258 来说:

| (挡板)表示从这里分开翻译, ,(逗号)表示分割多个翻译方式。

  • f(1) = 1,分别为 1。
  • f(2) = 2,分别为 1|2, 12。
  • f(3) = 3,分别为 1|2|2,1|22,12|2

其实对于 f(3) 来说, 我手动的情况下,是这么想的:

  • 先把 f(2) 结果搬过来,即 1|2,12
  • 在 f(2)的基础上分割,我要添加第三位,也就是一个 2 到末尾。 1|2|2 这样是行的, 12|2 同样是可以的。
  • 继续在 f(1) 的基础上分割,我要添加第三位,也就是一个 2 到末尾。 1|22

那么总的情况就是三种。OK,总结下我的逻辑:

  • 如果我不可以和前面的数字组成 10 - 25 之间的数,那么在 f(n - 1) 的末尾添加挡板
  • 如果可以,同时在 f(n - 1)和 f(n -2) 的末尾添加挡板

用图来表示:

因此,实际上这道题就是爬楼梯的换皮题。

代码

1
2
3
4
5
6
7
8
9
10
class Solution:
def translateNum(self, num: int) -> int:
@lru_cache
def helper(s: str) -> int:
if not s: return 1
pre = helper(s[:-1])
if 10 <= int(s[-2:]) <= 25:
return pre + helper(s[:-2])
return pre
return helper(str(num))

复杂度分析

  • 时间复杂度:最坏的情况,每一个数组都可以和前面的组成新的数组, 有大约 $2^N$ 种组合,因此时间复杂度为 $O(2^N)$,而我这里使用了 @lru_cache 因此不会有重复计算,时间复杂度为 $(N)$,其中 N 为 数字长度。
  • 空间复杂度:由于空间复杂的受递归调用栈的影响,因此空间复杂度为 $O(2^N)$,而我这里使用了 @lru_cache 因此不会有重复计算,空间复杂度为 $(N)$,其中 N 为 数字长度。

如果你愿意的话,其实优化起来也比较简单,我们只需要 bottom-up 即可。

1
2
3
4
5
6
7
8
9
10
class Solution:
def translateNum(self, num: int) -> int:
s = str(num)
n = len(s)
dp = [1] * n
for i in range(1, n):
dp[i] = dp[i - 1]
if 10 <= int(s[i - 1:i + 1]) <= 25:
dp[i] += dp[i - 2]
return dp[-1]

进而可以优化到空间 $O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def translateNum(self, num: int) -> int:
s = str(num)
n = len(s)
a = b = 1
for i in range(1, n):
if 10 <= int(s[i - 1:i + 1]) <= 25:
temp = a
a = b
b = temp + b
else:
a = b
return b

更多题解可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 30K star 啦。

大家也可以关注我的公众号《力扣加加》获取更多更新鲜的 LeetCode 题解


 评论


博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本站使用 Material X 作为主题 , 总访问量为 次 。
载入天数...载入时分秒...