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

约 4 分钟
文章信息 11 个分类 2 个标签
分类
LeetCode CodeTop 中等 未解决 10-20 字节跳动 微软 快手 猿辅导 剑指 Offer 剑指 Offer（第 2 版）
标签
字符串 动态规划
目录

题目描述

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

image-20241107211543206

题意分析

给一个非负整数 num，按 0 -> a、1 -> b、……、25 -> z 的规则把它翻译成字符串，问一共有多少种不同的翻译方法。

要什么：方法数，不是具体的翻译结果，所以不需要真的把字符串拼出来，只要计数。

关键的规则细节：每次可以取一位数字翻译，也可以取相邻两位当作一个整体翻译，但两位整体的取值必须落在 [0, 25] 且必须是这两位真实拼出来的数。这里有个必须点明的陷阱——10 到 25 可以作为两位整体翻译，但 06 这类带前导零的组合不行。因为 06 拼出来的数是 6，而 6 对应的编码是单个数字 "6"，写成 "06" 并不是一个合法的两位编码，翻译规则里根本不存在这种表示。同理 00 到 09 全都不能合并。所以两位合并的合法区间是 [10, 25]，既有上界也有下界。

约束信号：0 <= num < 2^31，十进制最多 10 位。位数这么少意味着答案不会太大（10 位数字最多也就 89 种翻译，是斐波那契量级），普通 int 完全装得下，不用担心溢出，也不用取模。同时它也提示这题的规模根本不是难点，难点在把规则翻译成正确的递推。

边界要想到：num = 0 时十进制串是 "0"，只有一种翻译，答案是 1；num 是个位数时答案恒为 1；串里出现 0 时这个 0 只能单独翻译成 a，不能被前一位吃掉；连续多位可合并时（比如 1212）方法数会像斐波那契一样累积。

解法：滚动动态规划

核心思路

递归会反复计算相同前缀，因此改用动态规划。令 dp[i] 表示前 i 位数字的翻译方案数，最后一次翻译只有两种选择：

  • 最后一位单独翻译，贡献 dp[i - 1]；单个 0..9 都合法。
  • 最后两位合并翻译，仅当它们组成 [10, 25] 内的数时成立，贡献 dp[i - 2]。

所以 dp[i] = dp[i - 1] + dp[i - 2]（两位合法），否则 dp[i] = dp[i - 1]。dp[0] = dp[1] = 1；每个方案按最后一段长度被唯一分类，因此转移不重不漏。状态只依赖前两项，用 pre、cur 滚动即可。

解题步骤

  1. 将数字转为十进制字符串，初始化 pre = 1、cur = 1，分别对应 dp[0]、dp[1]。
  2. 从第二位开始，计算当前相邻两位组成的数 twoDigits。
  3. 若 10 <= twoDigits <= 25，令 next = pre + cur；否则 next = cur。
  4. 用旧 cur 更新 pre，再令 cur = next，最终返回 cur。

例如 12258 的方案数依次为 1, 2, 3, 5, 5，答案为 5。06 不能合并，因为映射中没有带前导零的两位编码。

代码实现

class Solution {
    public int translateNum(int num) {
        String text = String.valueOf(num);
        int pre = 1;
        int cur = 1;
        for (int idx = 1; idx < text.length(); idx++) {
            int twoDigits = (text.charAt(idx - 1) - '0') * 10 + text.charAt(idx) - '0';
            int next = cur;
            // 只有 10 到 25 可以作为两位整体翻译，06 这类不能合并。
            if (twoDigits >= 10 && twoDigits <= 25) {
                next = pre + cur;
            }
            pre = cur;
            cur = next;
        }
        return cur;
    }
}

import "strconv"

func translateNum(num int) int {
    text := strconv.Itoa(num)
    pre, cur := 1, 1
    for idx := 1; idx < len(text); idx++ {
        twoDigits := int(text[idx-1]-'0')*10 + int(text[idx]-'0')
        next := cur
        // 只有 10 到 25 可以作为两位整体翻译，06 这类不能合并。
        if twoDigits >= 10 && twoDigits <= 25 {
            next = pre + cur
        }
        pre = cur
        cur = next
    }
    return cur
}

复杂度分析

  • 时间复杂度：$O(n)$，n 为十进制位数。
  • 空间复杂度：$O(n)$，用于十进制字符串；DP 状态为 $O(1)$。

关键点总结

  • 按最后一段长度分类，是计数 DP 的常见建模方式。
  • 合并区间必须是 [10, 25]；单个 0 合法，但 06 不合法。
  • dp[0] = 1 代表空前缀的一种完成方式，是两位整体翻译时的来源。
  • 与 91 题不同：本题映射范围为 0..25，而 91 题中单个 0 非法、两位上界为 26。

易错点总结

  • 只检查 twoDigits <= 25 会把 06 当成合法组合；506 应只有 1 种翻译。
  • 把上界写成 26 会错误接受 26。
  • 滚动更新顺序写反会覆盖上一轮状态，必须先计算 next。
  • 字符转数字时不要漏掉减 '0'。

相似题目

题目 难度 考察点
70. 爬楼梯 简单 无约束的一步/两步递推
91. 解码方法 中等 区间 [10, 26] 且 0 非法
198. 打家劫舍 中等 相邻互斥下的取最大值递推
509. 斐波那契数 简单 滚动变量压缩状态的最小样例
剑指 Offer 10- I. 斐波那契数列 简单 递推 + 取模防溢出