91. 解码方法 - 力扣LeetCode91. 解码方法 - 一条包含字母 A-Z 的消息通过以下映射进行了 编码 1 - A2 - B...25 - Y26 - Z然而在 解码 已编码的消息时你意识到有许多不同的方式来解码因为有些编码被包含在其它编码当中2 和 5 与 25。例如11106 可以映射为 * AAJF 将消息分组为 (1, 1, 10, 6) * KJF 将消息分组为 (11, 10, 6) * 消息不能分组为 (1, 11, 06) 因为 06 不是一个合法编码只有 6 是合法的。注意可能存在无法解码的字符串。给你一个只含数字的 非空 字符串 s 请计算并返回 解码 方法的 总数 。如果没有合法的方式解码整个字符串返回 0。题目数据保证答案肯定是一个 32 位 的整数。 示例 1输入s 12输出2解释它可以解码为 AB1 2或者 L12。示例 2输入s 226输出3解释它可以解码为 BZ (2 26), VF (22 6), 或者 BBF (2 2 6) 。示例 3输入s 06输出0解释06 无法映射到 F 因为存在前导零6 和 06 并不等价。 提示 * 1 s.length 100 * s 只包含数字并且可能包含前导零。https://leetcode.cn/problems/decode-ways/题目描述一条包含字母A-Z的消息通过以下映射进行编码A - 1 B - 2 ... Z - 26给定一个只包含数字的字符串s请计算一共有多少种解码方式。注意0无法单独映射成任何字母06不能当成6解码必须是10~26的两位数才合法。示例输入s 12输出21 2AB、12L输入s 226输出32 2 6、22 6、2 26输入s 06输出0开头 0 无法解码动态规划五步1. dp 数组定义dp[i]字符串前 i 个字符s[0] ~ s[i-1]拥有的解码方案总数。数组长度为n1dp[0]代表空字符串dp[n]就是整个字符串的答案。2. 状态转移逻辑我们处理前i个字符有两种合法解码分支单独解码最后一位如果s[i-1] ! 0这一位可以单独作为一个编码方案数继承dp[i-1]。两位合并解码取最后两位组成数字如果数值在10 ~ 26之间可以把这两位看成一个整体方案数继承dp[i-2]。3. dp 数组初始化dp[0] 1空串设置为 1是 DP 递推的基准。不是说空串有真实解码是为了两位合并计算时方便。dp[1]对应字符串第 1 个字符s[0]。如果s[0] 0直接无法解码dp[1]0否则dp[1]1。4. 遍历顺序dp[i]依赖dp[i-1]和dp[i-2]所以从左向右遍历i 从 2 循环到 n。5. 返回结果dp[n]前 n 个字符完整字符串的解码方案总数。#include vector #include string using namespace std; class Solution { public: int numDecodings(string s) { int n s.size(); vectorint dp(n 1); dp[0] 1; dp[1] (s[0] 0) ? 0 : 1; for(int i 2; i n; i) { dp[i] 0; // 当前位可以单独解码 if(s[i-1] ! 0){ dp[i] dp[i-1]; } // 判断最后两位是否10~26 int val (s[i-2] - 0) * 10 (s[i-1] - 0); if(val 10 val 26){ dp[i] dp[i-2]; } } return dp[n]; } };