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

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

题目描述

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

image-20261001230752571

题意分析

将非负整数的十进制数字从左到右分组，每组按 0..25 映射为一个字母，求不同翻译的数量。每组只能占一位或两位：单个数字都合法，两位组成的数必须在 10..25 内，不能带前导零。

解法：滚动动态规划

核心思路

[!blue]

令 dp[i] 表示前 i 位数字的翻译数量。观察最后一个字母用了几位，就能把所有方案分成互不重叠的两类：最后一位单独翻译，前面的 i - 1 位有 dp[i - 1] 种方案；最后两位整体翻译，则要求它们组成的数在 10..25 内，前面的 i - 2 位有 dp[i - 2] 种方案。

因而两位合法时，dp[i] = dp[i - 1] + dp[i - 2]；否则只有单独翻译末位这一种接法，dp[i] = dp[i - 1]。最后一组不可能超过两位，这两类已经覆盖全部方案；它们的分组位置不同，不会重复计数。

初值 dp[0] = 1 表示空前缀只有一种分组方式，保证开头两位整体翻译时能贡献一种方案；dp[1] = 1，因为单个数字包括 0 都可翻译。输入只有一位时无需转移，答案就是 1。

每次只依赖前两个状态，用 pre 和 cur 滚动保存。处理下标 idx 前，它们分别等于 dp[idx - 1] 和 dp[idx]；先求出 next = dp[idx + 1]，再同时向前推进，避免覆盖仍需使用的旧值。

解题步骤

  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。

代码实现

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)$。

关键点总结

[!green]

  • dp[i] 按前缀长度定义，转移只需判断末尾两位是否可以合并。
  • 单独翻译末位与合并末尾两位的方案互斥，所以两位合法时相加；不合法时仍保留单独翻译末位的方案。
  • dp[0] = 1 是计数起点，num = 0 也有一种翻译，不能返回 0。
  • 与 91 题不同：本题映射范围为 0..25，而 91 题中单个 0 非法、两位上界为 26。

易错点总结

[!yellow]

  • 两位组合必须同时满足下界 10 和上界 25，否则会错误接受前导零或超出映射范围的组合。
  • 单个 0 合法，不能套用“遇到零就无解”的判断。
  • 滚动更新顺序写反会覆盖上一轮状态，必须先计算 next。
  • 字符转数字时不要漏掉减 '0'。

相似题目

题目 难度 关联与区别
91. 解码方法 中等 原题映射1到26且0不能单独解码，本题映射0到25，单个0合法但双位26不合法。
70. 爬楼梯 简单 都可按消费1位或2位计数递推，但本题两位合并只在10到25之间合法。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/80659006
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！