剑指offer2之把数字翻译成字符串

题目(把数字翻译成字符串)

给定一个数字,我们按照如下的规则把它翻译为字符串:将 0-25 分别对应翻译到 a-z 字符,如 0 翻译成 a,以此类推。一个数字可能有多少种翻译。例如,12258 有 5 种不同的翻译,分别是 “bccfi”、”bwfi”、”bczi”、”mcfi”、”mzi”。请编程实现一个函数,用来计算一个数字有多少种不同的翻译方法。

算法思路

以 12258 为例,显然,从 1 开始翻译的种数包括了从第二个 2 开始翻译的种数,以及从第三个 2 开始翻译的总数,但是后者是有条件的,如果此例子中的 12 所在的位置是其他两位不在 10-25 之间的数字,那么此种情况无法翻译,那么该翻译方式就不统计了。显然,对于从 1 开始翻译,包含了两个递归子问题。那么对子问题的分析以此类推。这其实就是自顶向上分析问题。
那么既然是递归有无重叠子问题呢?从上述例子中,如果先翻译 1,再翻译 2,最后要翻译 258;如果先翻译 12,最后还是要翻译 258,这里就出现了重叠的子问题。

那么为了避免重叠子问题的计算,我们可以采用自底向上的计算方式,从后面开始翻译,因为从前面开始翻译的翻译总数可以由从后面开始翻译的翻译总数得到。

那么动态转移方程就是:
f(i)=f(i+1)+g(i,i+1)*f(i+2); g(i,i+1) 表示 i 和 i+1 位置上拼接的数字是否在 10-25 之内,因此其取值为 0 或者 1。

本题其实也是动态规划的一种,类似动态规划经典题青蛙跳台阶。

算法实现

复杂度

算法仅遍历一次输入数字对应的字符串,因此时间复杂度为 O(n);定义了记录翻译总数的数组,空间复杂度也为 O(n)。

参考

[1] <<剑指offer2>>

-------------本文结束感谢您的阅读-------------
Powered By Valine
v1.5.2