企业官网建设流程全解析

LeetCode 639 解码方法 II（Decode Ways II）

难度：Hard
标签：动态规划、字符串、分类讨论
题目链接：https://leetcode.cn/problems/decode-ways-ii

题目原文

一条包含字母A-Z的消息通过以下映射进行编码：

'A' -> "1" 'B' -> "2" ... 'Z' -> "26"

要解码已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"11106"可以映射为：

• "AAJF"，将消息分组为(1 1 10 6)
• "KJF"，将消息分组为(11 10 6)

注意，消息不能分组为(1 11 06)，因为"06"不能映射为"F"，这是由于"6"和"06"在映射中并不等价。

除了数字，编码消息中会包含字符*，*可以代表1~9中任意一位数字（不能代表0）。
给定字符串s，由数字和*组成，返回解码方法总数。
答案可能很大，返回对109+710^9+7109+7取模后的结果。

示例
示例1：
输入:"*"
输出:9
解释：*可以是1~9，对应A-I，共9种解码方式

示例2：
输入:"1*"
输出:18
解释：

1. 1单独解码，*单独解码：1 ×9 =9
2. 1和*合并，*可以是1_9，组成1119，共9种；合计18

示例3：
输入:"2*"
输出:15
解释：
单独解码：1 ×9 =9
合并解码：2后面只能是1_6，2126，共6；合计15

提示

• 1 <= s.length <= 10^5
• s[i]是数字0-9或者*

费曼学习法 完整拆解破解过程

费曼核心：把难题翻译成大白话，先搞懂基础，找递推关系，然后找出所有分类边界，再优化空间。

第一步：用大白话复述题目（讲给小白）

原来91题解码方法，只有数字；本题多了*通配符。
规则：

1. 一段数字可以单独1位解码（1~9有效，0无效）
2. 一段数字可以2位合并解码，必须在10~26之间才有效
3. *代表1~9任意数字，不能是0
4. 问一共有多少种分组解码方案。

核心思想：动态规划。dp[i]= 字符串前i个字符，一共有多少解码方案。
递推公式：
dp[i]=dp[i−1]×第i位单独解码的方案数+dp[i−2]×第i-1,i两位合并解码的方案数dp[i] = dp[i-1] \times \text{第i位单独解码的方案数} + dp[i-2] \times \text{第i-1,i两位合并解码的方案数}dp[i]=dp[i−1]×第i位单独解码的方案数+dp[i−2]×第i-1,i两位合并解码的方案数

第二步：拆解两个辅助计数函数（本题最难部分：分类）

① count1©：单个字符单独解码有多少种

• c == '*'→ 9种（1~9）
• c == '0'→ 0种，不能单独解码
• 普通数字1~9 → 1种

② count2(c1,c2)：c1和c2两个字符合并解码，有多少种

c1是前字符，c2是后字符，拼成两位数，范围必须 10~26

1. c1 == '*'并且c2 == '*'：
   可以是1或2；第二个：
   当c1=1，第二个*可以1_{9；c1=2，第二个*可以1}6 → 9+6=15种
2. c1 == '*'，c2是数字：
   • c2 ≤ ‘6’：*可以取1、2 →2种
   • c2 > ‘6’：*只能取1 →1种（17,18,19；27超26不行）
3. c2 == '*'，c1是数字：
   • c1 == ‘1’ → *取1~9 →9种
   • c1 == ‘2’ → *取1~6 →6种
   • 其他数字（3~9）→0种，3*=30+>26
4. 两个都是普通数字：
   拼成数字，>=10且<=26返回1，否则返回0

第三步：DP初始条件

dp[0]=1：空字符串，有1种解码方式（基准，方便计算）
dp[1]=count1(s[0])：前1个字符的解码数量

第四步：空间优化

字符串最长10510^5105，开完整dp数组没问题；但我们只需要前两项的值dp[i-1]、dp[i-2]，不需要保存全部数组。
只用两个变量保存前两个状态：prev1=dp[i-1], prev2=dp[i-2]，空间从O(n)降到O(1)。

坑点（费曼自查）

1. 随时取模，数字极大，必须% (10**9+7)，用long防止溢出（pythonint不会溢出，但取模不能忘）
2. *不能等于0，很多新手在这里错
3. 两位组合必须≥10，所以0x这种直接无效
4. 顺序不能颠倒，c1是左边字符，c2右边字符

第五步：现实应用场景举例

1. 加密消息解码：短信/密文编码，使用通配符模糊编码，统计所有可能原始消息数量；
2. 生物基因序列匹配：DNA序列含有模糊占位符*，统计合法片段组合数；
3. 验证码模糊识别：OCR识别验证码，部分字符识别不清标记为通配符，统计所有合法候选验证码数量；
4. 信号编码传输：通信传输部分比特丢失，用通配符代替，估算全部合法译码方案。

Python完整代码：版本1 DP数组写法，每行详细注释

classSolution:defnumDecodings(self,s:str)->int:# 模数，题目要求结果对10^9+7取模MOD=10**9+7# 获取字符串总长度n=len(s)# dp数组，dp[i]表示字符串前i个字符的解码方案总数# dp[0]代表空串，dp[1]前1字符，dp[n]是答案dp=[0]*(n+1)# 空字符串：基准条件，定义1种方式dp[0]=1# dp[1]：第一个字符单独解码数量dp[1]=self.count1(s[0])# 从i=2遍历到i=n，i代表前i个字符foriinrange(2,n+1):# 当前字符是s[i-1]（字符串下标从0开始）single_char=s[i-1]# 前一个字符s[i-2]pre_char=s[i-2]# 方案1：把当前字符单独解码，方案数=dp[i-1] * 单个字符的合法数量way1=dp[i-1]*self.count1(single_char)# 方案2：把前一个字符+当前字符合并为两位数解码，方案数=dp[i-2] *两位组合合法数量way2=dp[i-2]*self.count2(pre_char,single_char)# 总方案 = way1 + way2，取模dp[i]=(way1+way2)%MOD# 返回前n个字符的总解码方案returndp[n]# 辅助函数：单个字符单独解码，返回有多少种可能defcount1(self,c:str)->int:ifc=="*":# *可以是1~9，共9种return9elifc=="0":# 0不能单独解码，0种return0else:#普通数字1~9，1种return1# 辅助函数：两个字符c1(左边),c2(右边)合并成两位数解码，返回合法组合数量defcount2(self,c1:str,c2:str)->int:# 情况1：两个都是*ifc1=="*"andc2=="*":#11~19(9种),21~26(6种),合计15return15#情况2：左边是*，右边是普通数字elifc1=="*":ifc2<="6":#*可以取1或2，两种：1x，2x都<=26return2else:#c2>6，*只能取1，17,18,19；27>26不行return1#情况3：右边是*，左边普通数字elifc2=="*":ifc1=="1":#1* →11~19，9种return9elifc1=="2":#2* →21~26，6种return6else:#c1>=3，3*>=30>26，0种return0#情况4：两个都是普通数字else:#拼成整数two_num=int(c1)*10+int(c2)#10<=两位数<=26有效，返回1，否则0return1if10<=two_num<=26else0# ========= 测试用例 =========if__name__=="__main__":sol=Solution()print(sol.numDecodings("*"))#9print(sol.numDecodings("1*"))#18print(sol.numDecodings("2*"))#15

Python版本2：空间优化版O(1)（推荐，适合1e5长度字符串，面试首选）

classSolution:defnumDecodings(self,s:str)->int:MOD=10**9+7n=len(s)ifn==0:return0# prev2 = dp[i-2]，prev1=dp[i-1]# 初始化：dp[0]=1，dp[1]=count1(s[0])prev2=1prev1=self.count1(s[0])# 从第二个字符开始遍历，i是字符串下标foriinrange(1,n):c_curr=s[i]#当前字符c_prev=s[i-1]#前一个字符# 单独解码方案way1=prev1*self.count1(c_curr)# 两符合并解码方案way2=prev2*self.count2(c_prev,c_curr)# 当前dp值curr=(way1+way2)%MOD# 更新两个指针，滚动向前prev2=prev1 prev1=currreturnprev1defcount1(self,c:str)->int:ifc=="*":return9elifc=="0":return0return1defcount2(self,c1:str,c2:str)->int:ifc1=="*"andc2=="*":return15elifc1=="*":return2ifc2<="6"else1elifc2=="*":ifc1=="1":return9elifc1=="2":return6else:return0else:num=int(c1)*10+int(c2)return1if10<=num<=26else0#测试if__name__=="__main__":obj=Solution()print(obj.numDecodings("*"))print(obj.numDecodings("1*"))print(obj.numDecodings("2*"))print(obj.numDecodings("**"))#15

复杂度：

• 时间复杂度O(n)，n字符串长度，只遍历一次字符串
• 空间优化版O(1)，只用3个变量，适合1e5超大字符串，不会内存爆炸

费曼复盘总结

本题本质是91解码方法的升级版，动态规划递推公式没变，难点全部落在*的各种分类讨论。
做题思路顺序：

1. 先写出DP递推公式；
2. 单独写count1、count2，把所有星号情况枚举清楚；
3. 处理取模，防止数值过大；
4. 空间优化，压缩DP数组为滚动变量。