LeetCode 91. 解码方法

2026-09-22 HGNULB 约 5 分钟

文章信息 17 个分类 2 个标签

分类

LeetCode CodeTop 中等未解决 20-50 腾讯字节阿里华为微软亚马逊美团拼多多网易快手虾皮商汤

题目描述

✅ 91. 解码方法

题意分析

数字串按 1..26 分别映射到 A..Z，要求把整个字符串划分成若干个合法编码，统计不同划分方式的数量。必须按原顺序用完所有字符，不能跳过字符，也不是求一个解码结果。

一个编码只能占一位或两位。单独的 0 没有对应字母，两位编码必须在 10..26 之间，不能带前导零；同一个位置可能既能单独解码，也能与前一位合并，这两种选择都需要计数。

解法：滚动动态规划统计解码数

核心思路

[!blue]

定义 dp[k] 为前 k 个字符的合法解码方案数。按最后一个编码占几位，可以把所有方案分成两类，剩下的部分恰好都是更短前缀的同类问题。

如果末位不是 0，可以把它单独解码。前 k - 1 个字符的每一种合法划分，都能在末尾追加这个编码，所以贡献 dp[k - 1]。如果末两位组成的数在 10..26 内，可以把它们整体解码，前 k - 2 个字符的每一种方案都能接上这一组，贡献 dp[k - 2]。

两类方案的最后一个编码长度不同，因此不会重复，合法时应该相加。若某个分支不合法就没有贡献；两种都不合法时，当前前缀的方案数为 0。这样零的限制已经包含在递推条件中，无需把所有含零的字符串直接判错。

空前缀设为 dp[0] = 1，表示“前面什么也不选”的唯一划分，它让第一个两位编码能够从空前缀接出一种方案。首字符若为 0，不存在合法起点，直接返回 0；否则 dp[1] = 1。

每个新状态只依赖前两个状态，所以用 pre1 保存较长前缀的计数、pre2 保存再短一个字符的计数。每轮从 cur = 0 开始分别累加两个合法分支，再滚动保存，避免把上一轮的结果无条件带入。

解题步骤

检查首字符。如果是 0，直接返回 0。

初始化 pre2 = dp[0] = 1、pre1 = dp[1] = 1。

从下标 i = 1 开始，令 cur = 0。当前字符非零，就加上 pre1。

读取前一位与当前位组成的两位数，若位于 10..26，再加上 pre2。

先把旧 pre1 保存给 pre2，再令 pre1 = cur，继续扩展前缀。

处理完后返回 pre1，它就是整个字符串的解码数量。

代码实现

class Solution {
    public int numDecodings(String s) {
        if (s.charAt(0) == '0') {
            return 0;
        }

        int pre2 = 1;
        int pre1 = 1;

        for (int i = 1; i < s.length(); i++) {
            int cur = 0;

            if (s.charAt(i) != '0') {
                // 非零数字可以单独解码，继承前一前缀的方案数。
                cur += pre1;
            }

            int twoDigits = (s.charAt(i - 1) - '0') * 10 + s.charAt(i) - '0';

            // 两位整体必须在十至二十六之间，零只能参与合法两位编码。
            if (twoDigits >= 10 && twoDigits <= 26) {
                cur += pre2;
            }

            pre2 = pre1;
            pre1 = cur;
        }

        return pre1;
    }
}

func numDecodings(s string) int {
    if s[0] == '0' {
        return 0
    }

    pre2, pre1 := 1, 1
    for i := 1; i < len(s); i++ {
        cur := 0
        if s[i] != '0' {
            // 非零数字可以单独解码，继承前一前缀的方案数。
            cur += pre1
        }

        twoDigits := int(s[i-1]-'0')*10 + int(s[i]-'0')
        // 两位整体必须在十至二十六之间，零只能参与合法两位编码。
        if twoDigits >= 10 && twoDigits <= 26 {
            cur += pre2
        }

        pre2, pre1 = pre1, cur
    }
    return pre1
}

复杂度分析

时间复杂度：$O(n)$，只从左到右扫描一次字符串，每个位置做常数次判断和加法。

空间复杂度：$O(1)$，只保存相邻两个 DP 状态和当前值。

关键点总结

[!green]

按最后一组编码长度分类，既覆盖全部方案，又保证两类计数不重复。

dp[0] = 1 是空划分作为起点的计数，不是把空串映射成某个字母。

单字符与双字符合法性需要分别判断，两者可能同时贡献，不能互相排斥。

易错点总结

[!yellow]

无条件加入单字符贡献，会把没有字母对应的 0 也当作编码。

两位数只检查不超过 26，会错误接受带前导零的组合；还必须至少为 10。

将 dp[0] 设为 0，会漏掉从字符串开头直接取一个两位编码的方案。

用 if / else if 只选择一个合法分支，会丢失另一种结尾方式；两个贡献应独立累加。

不在每轮把 cur 归零，会沿用并不存在的旧方案。

先覆盖 pre1 再赋给 pre2，会把两个历史状态都变成新值，破坏后续递推。

相似题目

题目	难度	关联与区别
639. 解码方法 II	困难	在数字解码基础上增加星号通配符，单字符与双字符的匹配数量都需重新统计。
70. 爬楼梯	简单	同样存在消费1位或2位的递推，本题还必须检查数值范围与前导零，不能无条件相加。
746. 使用最小花费爬楼梯	简单	按最后一段长度递推前缀方案数；本题最后编码可占一位或两位，该题转为达到当前台阶的最小费用。
1137. 第 N 个泰波那契数	简单	按最后一段长度递推前缀方案数；本题最后编码可占一位或两位，该题依赖前三个状态。
补充题 182. 数字字符串的所有解码结果	中等	输出数字字符串的所有解码，具体要求如下。；沿用相关状态或数据结构，题面与输出要求见该篇。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2026/38032399

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！