Poison

剑指 Offer 46. 把数字翻译成字符串

DP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public int translateNum(int num) {
String str = String.valueOf(num);

// 定义 dp[i] 为第 i 个字符结尾的数字的方案数,此时 i 从 1 开始
int[] dp = new int[str.length() + 1];
dp[0] = 1;
dp[1] = 1;

// 此处注意 i 从 1 开始,故访问 str 时需要减去 1
for (int i = 2; i <= str.length(); i++) {
char x = str.charAt(i - 2), y = str.charAt(i - 1);
if (x == '1' || (x == '2' && y <= '5')) {
dp[i] = dp[i - 1] + dp[i - 2];
} else {
dp[i] = dp[i - 1];
}
}

return dp[str.length()];
}
}
DP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public int translateNum(int num) {
String numStr = String.valueOf(num);

// 定义 dp[i] 表示截止至 numStr[i] 的翻译方法数
int[] dp = new int[numStr.length()];
dp[0] = 1;

for (int i = 1; i < numStr.length(); i++) {
// 作为一个字符进行翻译时
dp[i] += dp[i - 1];

// 作为两个字符进行翻译时,'10' -> '25'
char p = numStr.charAt(i - 1), c = numStr.charAt(i);
if (p == '1' || (p == '2' && (c >= '0' && c <= '5'))) {
dp[i] += i - 2 >= 0 ? dp[i - 2] : 1;
}
}

return dp[numStr.length() - 1];
}
}
Reference

剑指 Offer 46. 把数字翻译成字符串