LeetCode 639 解码方法 IIDecode 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由数字和*组成返回解码方法总数。答案可能很大返回对109710^971097取模后的结果。示例示例1输入:*输出:9解释*可以是1~9对应A-I共9种解码方式示例2输入:1*输出:18解释1单独解码*单独解码1 ×9 91和*合并*可以是19组成1119共9种合计18示例3输入:2*输出:15解释单独解码1 ×9 9合并解码2后面只能是162126共6合计15提示1 s.length 10^5s[i]是数字0-9或者*费曼学习法 完整拆解破解过程费曼核心把难题翻译成大白话先搞懂基础找递推关系然后找出所有分类边界再优化空间。第一步用大白话复述题目讲给小白原来91题解码方法只有数字本题多了*通配符。规则一段数字可以单独1位解码1~9有效0无效一段数字可以2位合并解码必须在10~26之间才有效*代表1~9任意数字不能是0问一共有多少种分组解码方案。核心思想动态规划。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~9c 0→ 0种不能单独解码普通数字1~9 → 1种② count2(c1,c2)c1和c2两个字符合并解码有多少种c1是前字符c2是后字符拼成两位数范围必须 10~26c1 *并且c2 *可以是1或2第二个当c11第二个*可以19c12第二个*可以16 → 9615种c1 *c2是数字c2 ≤ ‘6’*可以取1、2 →2种c2 ‘6’*只能取1 →1种17,18,1927超26不行c2 *c1是数字c1 ‘1’ → *取1~9 →9种c1 ‘2’ → *取1~6 →6种其他数字3~9→0种3*3026两个都是普通数字拼成数字10且26返回1否则返回0第三步DP初始条件dp[0]1空字符串有1种解码方式基准方便计算dp[1]count1(s[0])前1个字符的解码数量第四步空间优化字符串最长10510^5105开完整dp数组没问题但我们只需要前两项的值dp[i-1]、dp[i-2]不需要保存全部数组。只用两个变量保存前两个状态prev1dp[i-1], prev2dp[i-2]空间从O(n)降到O(1)。坑点费曼自查随时取模数字极大必须% (10**97)用long防止溢出pythonint不会溢出但取模不能忘*不能等于0很多新手在这里错两位组合必须≥10所以0x这种直接无效顺序不能颠倒c1是左边字符c2右边字符第五步现实应用场景举例加密消息解码短信/密文编码使用通配符模糊编码统计所有可能原始消息数量生物基因序列匹配DNA序列含有模糊占位符*统计合法片段组合数验证码模糊识别OCR识别验证码部分字符识别不清标记为通配符统计所有合法候选验证码数量信号编码传输通信传输部分比特丢失用通配符代替估算全部合法译码方案。Python完整代码版本1 DP数组写法每行详细注释classSolution:defnumDecodings(self,s:str)-int:# 模数题目要求结果对10^97取模MOD10**97# 获取字符串总长度nlen(s)# dp数组dp[i]表示字符串前i个字符的解码方案总数# dp[0]代表空串dp[1]前1字符dp[n]是答案dp[0]*(n1)# 空字符串基准条件定义1种方式dp[0]1# dp[1]第一个字符单独解码数量dp[1]self.count1(s[0])# 从i2遍历到ini代表前i个字符foriinrange(2,n1):# 当前字符是s[i-1]字符串下标从0开始single_chars[i-1]# 前一个字符s[i-2]pre_chars[i-2]# 方案1把当前字符单独解码方案数dp[i-1] * 单个字符的合法数量way1dp[i-1]*self.count1(single_char)# 方案2把前一个字符当前字符合并为两位数解码方案数dp[i-2] *两位组合合法数量way2dp[i-2]*self.count2(pre_char,single_char)# 总方案 way1 way2取模dp[i](way1way2)%MOD# 返回前n个字符的总解码方案returndp[n]# 辅助函数单个字符单独解码返回有多少种可能defcount1(self,c:str)-int:ifc*:# *可以是1~9共9种return9elifc0:# 0不能单独解码0种return0else:#普通数字1~91种return1# 辅助函数两个字符c1(左边),c2(右边)合并成两位数解码返回合法组合数量defcount2(self,c1:str,c2:str)-int:# 情况1两个都是*ifc1*andc2*:#11~19(9种),21~26(6种),合计15return15#情况2左边是*右边是普通数字elifc1*:ifc26:#*可以取1或2两种1x2x都26return2else:#c26*只能取117,18,192726不行return1#情况3右边是*左边普通数字elifc2*:ifc11:#1* →11~199种return9elifc12:#2* →21~266种return6else:#c133*30260种return0#情况4两个都是普通数字else:#拼成整数two_numint(c1)*10int(c2)#10两位数26有效返回1否则0return1if10two_num26else0# 测试用例 if__name____main__:solSolution()print(sol.numDecodings(*))#9print(sol.numDecodings(1*))#18print(sol.numDecodings(2*))#15Python版本2空间优化版O(1)推荐适合1e5长度字符串面试首选classSolution:defnumDecodings(self,s:str)-int:MOD10**97nlen(s)ifn0:return0# prev2 dp[i-2]prev1dp[i-1]# 初始化dp[0]1dp[1]count1(s[0])prev21prev1self.count1(s[0])# 从第二个字符开始遍历i是字符串下标foriinrange(1,n):c_currs[i]#当前字符c_prevs[i-1]#前一个字符# 单独解码方案way1prev1*self.count1(c_curr)# 两符合并解码方案way2prev2*self.count2(c_prev,c_curr)# 当前dp值curr(way1way2)%MOD# 更新两个指针滚动向前prev2prev1 prev1currreturnprev1defcount1(self,c:str)-int:ifc*:return9elifc0:return0return1defcount2(self,c1:str,c2:str)-int:ifc1*andc2*:return15elifc1*:return2ifc26else1elifc2*:ifc11:return9elifc12:return6else:return0else:numint(c1)*10int(c2)return1if10num26else0#测试if__name____main__:objSolution()print(obj.numDecodings(*))print(obj.numDecodings(1*))print(obj.numDecodings(2*))print(obj.numDecodings(**))#15复杂度时间复杂度O(n)n字符串长度只遍历一次字符串空间优化版O(1)只用3个变量适合1e5超大字符串不会内存爆炸费曼复盘总结本题本质是91解码方法的升级版动态规划递推公式没变难点全部落在*的各种分类讨论。做题思路顺序先写出DP递推公式单独写count1、count2把所有星号情况枚举清楚处理取模防止数值过大空间优化压缩DP数组为滚动变量。