把数字翻译成字符串 -- java
题目描述
给定一个数字，我们按照如下规则翻译成字符串：0 翻译成“a”，1 翻译成“b”… 25 翻译成“z”。一个数字有多种翻译可能，例如 12258 一共有 5 种，分别是 bccfi，bwfi，bczi，mcfi，mzi。实现一个函数，用来计算一个数字有多少种不同的翻译方法。
解题思路
动态规划
假设数组dp[i]表示从头到字符串的第i位(不是字符串的下标)，一共有多少种解码方法的话
首先我们一定能从第i-1位的解码方法上继续解码。那么就是dp[i] += dp[i-1];
除此之外如果字符串的第i-1位和第i位能组成一个10到25的数字，说明我们可以是在第i-2位的解码方法上继续解码。那么就是dp[i] += dp[i-2];
代码
public class getTranslationCount {
public static int getTranslationCount(int number) {
String s = String.valueOf(number);
// 存储动态规划中间值
int[] dp = new int[s.length()+1];
// 为了dp[2] += dp[0] 而设置
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= s.length(); i++) {
// 1. 肯定会发生
dp[i] += dp[i-1];
// 2. 当前位与前一位可以组成一个数字时
int converted = Integer.parseInt(s.substring(i-2,i));
if (converted >=0 && converted <=25) {
dp[i] += dp[i-2];
}
}
return dp[s.length()];
}
public static void main(String[] args) {
System.out.println(getTranslationCount(12258));
}
}
来自：
《剑指Offer》
Coding-Interviews/把数字翻译成字符串.md at master · todorex/Coding-Interviews