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

题目：给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

样例：

输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是"bccfi", “bwfi”, “bczi”, “mcfi"和"mzi”

其中：0≤num<2310 \leq num < 2^{31}

思路：动态规划题的核心是找到状态转移方程，以及定义好初始状态。

定义：dp[i]表示第i个数字结尾的方案数，那么转移方程有两种情况：

  1. 当xix_i和xi−1x_{i-1}两个数字可以被翻译，即在[10, 25]区间内，dp[i]=dp[i−1]+dp[i−2]dp[i] = dp[i - 1] + dp[i - 2]
  2. 当xix_i和xi−1x_{i-1}两个数字不能被翻译，dp[i]=dp[i−1]dp[i] = dp[i - 1]

可以看到dp[i]的值仅和前两个dp值有关，因此可以优化空间数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int translateNum(int num) {
        String str = String.valueOf(num);
        int n = str.length();
        if (n < 2) return n;
        char[] c = str.toCharArray();
        int dp1 = 1;
        int dp2 = 1;
        int ans = 0;
        for (int i = 2; i <= n; i++) {
            int a = (c[i - 2] - '0') * 10 + (c[i - 1] - '0');
            ans = 10 <= a && a <= 25 ? dp1 + dp2 : dp2;
            dp1 = dp2;
            dp2 = ans;
        }
        return ans;
    }
}