解码方法 图解题解

解码方法这道题到底在数什么

给一串数字 s，1 对 A、2 对 B、直到 26 对 Z。切成若干段、每段是 1~26 的数字，就还原一种字母串，问能解出多少种。226 可切成 2|2|6、22|6、2|26，答案是 3。要的是方案总数，不是某一种切法，是道计数题。

为什么不能把所有切法都试一遍

递归枚举切点：当前位既能单独成段，也能和前一位凑成两位段，一路分叉。每往前一位多一次二选一，切法随长度指数膨胀，串一长数不完，病根是同一个后缀（从某位到结尾的那截）被反复重算。换个记账法：只盯「前 i 位有几种方案」，算过存下来复用，指数枚举就压成线性递推（用前面算好的值一步步推出后面的）。

dp[i] 定成前 i 位的方案数，dp[0] 为什么是 1

定义 dp[i] 为「s 前 i 位的解码方案数」，i 数的是位数、不是字符下标。dp[0] = 1 代表空串——还没解出字母，算一种空方案；它不是真有字母，而是给「末两位合并」当基准：合并时前面剩的正好是空串，靠它记上一票。dp[1] 看首位，非 '0' 就能单独成字母，dp[1] = 1。

两条来路怎么相加，'0' 又卡在哪

算 dp[i] 时，落到第 i 位的最后一步有两种来路。一是末位单独成字母，前提是 s[i] 不是 '0'（没有字母配 0），成立就继承 dp[i-1]；二是末两位合并成字母，前提是这个两位数在 10~26，成立就加 dp[i-2]。两条末段长度不同，不会数重，相加即全部。

'0' 的坑全从这两个前提长出来。单独的 '0' 解不了，末位是 '0' 时第一条来路作废；两位数要不小于 10，'06' 带前导 0 不在 10~26，第二条也作废。某个 '0' 两条全断整串无解，比如 '30'：0 不能单独、30 又超 26。开头 '0' 同理，第一位无字母可对，返回 0。

拿 226122618 亲手把 dp 填一遍

空串 dp[0] = 1，'2' 非 0 得 dp[1] = 1。第 2 位 '2'：继承 1，末两位 22 在 10~26 加 1，dp[2] = 2。第 3 位 '6'：继承 2，26 加 1，dp[3] = 3。第 4 位 '1'：继承 3，61 超 26 作废，dp[4] = 3。第 5 位 '2'：继承 3，12 加 3，dp[5] = 6。第 6 位 '2'：继承 6，22 加 3，dp[6] = 9。第 7 位 '6'：继承 9，26 加 6，dp[7] = 15。第 8 位 '1'：继承 15，61 超 26 作废，dp[8] = 15。第 9 位 '8'：继承 15，18 加 15，dp[9] = 30，就是整串答案。

复杂度是多少，哪些 '0' 的边界最坑

从第 2 位推到第 n 位，每位只做常数次判断，时间 O(n)；dp[i] 只依赖 dp[i-1] 和 dp[i-2]，两个变量轮替就够，不必存整张表，空间 O(1)。参考代码的 a、b 就是这两项。

另两个易错点：两位数要卡死 10~26 两头，'09' 小于 10 非法、'27' 大于 26 只能拆开；别把 dp[0] 当真有字母，它只是空串那一票基准。

Python

def numDecodings(s: str) -> int:
    if not s or s[0] == "0": return 0
    a, b = 1, 1   # dp[i-2], dp[i-1]
    for i in range(1, len(s)):
        cur = b if s[i] != "0" else 0
        if 10 <= int(s[i-1:i+1]) <= 26: cur += a
        a, b = b, cur
    return b

C++

int numDecodings(string s){
    if(s.empty() || s[0]=='0') return 0;
    int a = 1, b = 1;            // dp[i-2], dp[i-1]
    for(int i = 1; i < (int)s.size(); ++i){
        int cur = s[i]!='0' ? b : 0;
        int two = (s[i-1]-'0')*10 + (s[i]-'0');
        if(two >= 10 && two <= 26) cur += a;
        a = b; b = cur;
    }
    return b;
}

Java

int numDecodings(String s){
    if(s.isEmpty() || s.charAt(0)=='0') return 0;
    int a = 1, b = 1;            // dp[i-2], dp[i-1]
    for(int i = 1; i < s.length(); i++){
        int cur = s.charAt(i)!='0' ? b : 0;
        int two = (s.charAt(i-1)-'0')*10 + (s.charAt(i)-'0');
        if(two >= 10 && two <= 26) cur += a;
        a = b; b = cur;
    }
    return b;
}