1. 题目描述
给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
示例 1:
输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是"bccfi", “bwfi”, “bczi”, “mcfi"和"mzi”
2. 题目分析
- 这个题目类型和跳台阶差不多，一阶或者两阶的跳，求到N阶有多少种方法
- 对于12258来说，可拆分为以下几部分：1 2 2 5 8 、 12 2 5 8 、 12 25 8 、1 22 5 8 、1 2 25 8
- 相当于从1开始往后跳，一个数或者两个数（注意取值范围 0~25）
- 当前如果是N阶的话，可以F(n - 1) + 1或者F(n - 2)+2
F(n) = F(n-1) + F(n-2);
这里需要注意一下，当前获取的数字只有在10~25之间才是有效的，否则是无效的
3. 题目代码
class Solution { public static int translateNum(int num) { // 将num转为String类型 String string = String.valueOf(num); // 如果当前的数字小于10的话，证明只有一种结果，直接返回1 if (num < 10) { return 1; } int[] dp = new int[string.length() + 1]; dp[0] = 1; dp[1] = 1; for (int i = 2; i < string.length(); i++) { String x = string.substring(i - 2, i); if (x.compareTo("10") >= 0 && x.compareTo("25") <= 0) { dp[i] = dp[i - 1] + dp[i - 2]; } else { dp[i] = dp[i - 1]; } } return dp[string.length() - 1]; }
