题目
给定一个数字,按照如下规则翻译成字符串:0 翻译成“a”,1
翻译成“b”
… 25
翻译成“z”
。一个数字有多种翻译可能,例如12258
一共有5
种,分别是bccfi
,bwfi
,bczi
,mcfi
,mzi
。实现一个函数,用来计算一个数字有多少种不同的翻译方法。
解题思路
- 定义
\(f(i)\)
表示第
i
位有多少种翻译的方法,动态规划方程: \(f(i)=f(i+1)+g(i,i+1) \times f(i+2)\) - 其中
\(g(i,i+1)\)
表示
i,i+1
是否能组成10 ~ 25
public int translateNumToStr(int num) {
char[] str = String.valueOf(num).toCharArray();
int[] res = new int[str.length];
for (int i = str.length - 1; i >= 0; i--) {
if (i + 1 >= str.length) {
res[i] = 1;
continue;
}
res[i] = res[i + 1];
if (i + 2 < str.length && str[i] <= '2' && str[i] >= '1' && str[i + 1] <= '5') {
res[i] += res[i + 2];
}
}
return res[0];
}