题目

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

image.png

思路

只有一位数字，编码方案f(1）有1种；
有两位数字，编码方案可以可以有1种（每一位单独编码），或者2种（当这两位组成的数字位于【10,25】之间）
三位数字：

  • f(3) = f(2) + f(1) ———-f(2)表示第3位单独翻译；f(1)表示23位一起翻译（当这两位组成的数字位于【10,25】之间）
  • f(3) = f(2) ———-2、3位组成的数字位于不在【10,25】之间

……
因此，f(n) = f(n-1) + f(n-2)或者f(n) = f(n-1)。

代码

  1. class Solution:
  2.     def translateNum(self, num: int) -> int:
  3.         num = str(num)
  4.         length = len(num)
  6.         a, b = 1, 1
  7.         for i in range(1, length):
  8.             if 10 <= int(num[i-1:i+1]) <= 25:
  9.                 a, b = b, a+b
  10.             else:
  11.                 a, b = b, b
  13.         return b
  1. class Solution:
  2.     def translateNum(self, num: int) -> int:
  3.         num = str(num)
  4.         length = len(num)
  5.         memo = [0]*(length)
  6.         memo[0] = 1 # 只有一个数字，只有一种翻译
  7.         if length == 1:
  8.             return memo[0]
  9.         if 10 <= int(num[:2]) <= 25:
  10.             memo[1] = 2
  11.         else:
  12.             memo[1] = 1
  15.         for i in range(2, length):
  16.             if  10 <= int(num[i-1:i+1]) <= 25:
  17.                 memo[i] = memo[i-1] + memo[i-2]
  18.             else:
  19.                 memo[i] = memo[i-1]
  21.         return memo[-1]