LeetCode 91 Decode Ways 解码方式计数从递归到动态规划的四种递进解法附多语言源码【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode导读本文围绕 LeetCode 第 91 题「Decode Ways」展开讲解如何统计一条仅含数字的字符串可以被映射为字母A–Z对应1–26的所有合法解码方式。文章以仓库内 hints/decode-ways.md 的解题提示为主线完整继承其关于复杂度目标、决策树递推关系、备忘录缓存与边界条件的四个递进式提示并结合 articles/decode-ways.md 的详细推导给出从朴素递归$O(2^n)$到记忆化搜索、自底向上 DP、空间优化 DP$O(n)$ 时间 / $O(1)$ 空间的完整演进路径。读完本文你将掌握该题的递推建模、两种 DP 实现范式以及前导零等边界陷阱的规避方法并能对照仓库中 C、C、Go、Java、JavaScript、Python、Rust、TypeScript 等多语言实现进行交叉验证。1. 问题定义与字母映射规则题目给出一条只包含数字字符的字符串s要求返回所有可能的解码方法总数。映射规则为1→A2→B…26→Z也就是说一个映射值可以是1 位数字1–9也可以是2 位数字10–26。仓库中 cpp/0091-decode-ways.cpp 的文件头注释给出了两个直观示例s 12→ 2 种AB1 2或L12s 226→ 3 种2 26、22 6、2 2 6关键约束来自 articles/decode-ways.md 的 Prerequisites 与递归章节单数字解码s[i]不能为0因为没有任何字母映射到0双数字解码s[i:i2]必须落在10–26区间内字符串中的0只能作为双数字的第二位如10、20出现否则该子串不可解码。2. 复杂度目标以 $O(n)$ 时间和 $O(n)$ 空间为基准hints/decode-ways.md 的开篇提示Recommended Time Space Complexity明确要求目标解法应达到或优于$O(n)$ 时间、$O(n)$ 空间其中n为给定字符串长度。这一目标直接决定了思路走向$O(n)$ 意味着不能枚举全部解码组合那是 $O(2^n)$必须利用子问题的重叠性做动态规划或记忆化搜索。后文四种解法正是围绕如何从 $O(2^n)$ 收敛到 $O(n)$展开的。3. 建模核心决策树与递推关系Hint 1 Hint 23.1 每个位置只有两种选择hints/decode-ways.md 的 Hint 1 指出由于映射值最多 2 位扫描字符串时可以把一个或两个连续数字组合起来探索所有可能的解码路径这本质是一棵决策树。在任意下标i处只有两种选择取一位s[i]要求s[i] ! 0取两位s[i:i2]要求数值落在10–26。3.2 递推关系Hint 2 进一步给出递推骨架从下标i开始解码的方式数等于$$dfs(i) dfs(i 1) dfs(i 2)$$其中dfs(i 1)对应取一位分支dfs(i 2)对应取两位分支。但并不是每次两个分支都合法——前导零、超过26的两位数都构成非法路径这正是后文边界条件的重点。以s 226为例的决策树由 articles/decode-ways.md 的递归直觉推导dfs(0) 226 ├── 取一位 2 → dfs(1) 26 │ ├── 取一位 2 → dfs(2) 6 → 取一位 6 → dfs(3) 1 (2-2-6) │ └── 取两位 26 → dfs(3) 1 (2-26) └── 取两位 22 → dfs(2) 6 → 取一位 6 → dfs(3) 1 (22-6) 合计 34. 解法一朴素递归Brute Force DFS4.1 基例与递归逻辑articles/decode-ways.md 的递归章节给出的算法骨架定义dfs(i) 解码s[i:]的方式数基例i len(s)→ 返回1整串解码完成当前路径计 1 次s[i] 0→ 返回0非法起点递归求和先取一位dfs(i 1)若两位数字合法10–26再加dfs(i 2)从dfs(0)开始。Python 实现与 python/0091-decode-ways.py 中的递归思路一致class Solution: def numDecodings(self, s: str) - int: def dfs(i): if i len(s): return 1 if s[i] 0: return 0 res dfs(i 1) if i len(s) - 1: if (s[i] 1 or (s[i] 2 and s[i 1] 7)): res dfs(i 2) return res return dfs(0)4.2 复杂度$O(2^n)$ 的指数灾难递归每次至多分叉两次最坏情况下如全1串会形成指数级调用树。但注意大量调用携带相同的参数i重复计算同一子问题。时间复杂度$O(2^n)$来自 articles/decode-ways.md 递归章节hints/decode-ways.md 的 Hint 3 也明确指出暴力递归为 $O(2^n)$空间复杂度$O(n)$递归调用栈深度这一版本适合理解递推本质但无法通过大规模测试用例必须消除重复计算。5. 解法二自顶向下 DP记忆化搜索5.1 核心观察子问题重叠hints/decode-ways.md 的 Hint 3 与 Hint 4 给出两条关键指引Hint 3考虑重复调用同参数递归造成的重复工作想办法避免它并思考递归函数的基例Hint 4基例是i越界时返回1当前位为0时返回0使用数组或哈希表缓存递归结果命中缓存直接返回。5.2 算法步骤用字典dp记录dp[i] 解码s[i:]的方式数初始化dp[len(s)] 1空串视为 1 种合法解码对应基例dfs(i)命中缓存直接返回s[i] 0返回0否则计算dfs(i 1)两位数合法时加dfs(i 2)结果存入dp[i]后返回最终调用dfs(0)。Python 实现即 python/0091-decode-ways.py 的 Memoization 版本class Solution: def numDecodings(self, s: str) - int: dp {len(s): 1} def dfs(i): if i in dp: return dp[i] if s[i] 0: return 0 res dfs(i 1) if i 1 len(s) and ( s[i] 1 or s[i] 2 and s[i 1] in 0123456 ): res dfs(i 2) dp[i] res return res return dfs(0)注意两位数的合法性判断有两种等价写法articles/decode-ways.md 中多语言版本均有体现字符比较法s[i] 1 or (s[i] 2 and s[i 1] 7)集合包含法s[i] 1 or s[i] 2 and s[i 1] in 0123456两者都精确限定两位数字在10–26区间以1开头时第二位可为0–9以2开头时第二位只能是0–6。5.3 复杂度时间复杂度$O(n)$——每个下标至多计算一次空间复杂度$O(n)$——缓存字典或数组加递归栈。仓库的 go/0091-decode-ways.go 提供了用切片dp代替哈希表的记忆化实现rust/0091-decode-ways.rs 则用VecOptioni32区分未计算与已缓存状态可作为不同语言惯用写法的参考。6. 解法三自底向上 DPTabulation6.1 反转视角自底向上不再递归而是从后往前构建答案articles/decode-ways.md 的 Bottom-Up 章节dp[i] 解码子串s[i:]的方式数最终答案是dp[0]每个位置只依赖其后1 或 2 个位置天然适合迭代填表。6.2 算法步骤建立 DP 表基例dp[len(s)] 1从i len(s) - 1向左迭代s[i] 0→dp[i] 0否则dp[i] dp[i 1]取一位若两位数合法则再加dp[i 2]返回dp[0]。Python 实现即 python/0091-decode-ways.py 的 Dynamic Programming 版本class Solution: def numDecodings(self, s: str) - int: dp {len(s): 1} for i in range(len(s) - 1, -1, -1): if s[i] 0: dp[i] 0 else: dp[i] dp[i 1] if i 1 len(s) and ( s[i] 1 or s[i] 2 and s[i 1] in 0123456 ): dp[i] dp[i 2] return dp[0]6.3 另一种等价视角从前往后仓库 cpp/0091-decode-ways.cpp 采用从前向后的递推写法递推关系为dp[i] dp[i-1] (若 s[i-1] 是 1~9) dp[i] dp[i-2] (若 s[i-2:i] 是 10~26)class Solution { public: int numDecodings(string s) { if (s[0] 0) { return 0; } int n s.size(); vectorint dp(n 1); dp[0] 1; dp[1] 1; for (int i 2; i n; i) { int ones stoi(s.substr(i - 1, 1)); if (ones 1 ones 9) { dp[i] dp[i - 1]; } int tens stoi(s.substr(i - 2, 2)); if (tens 10 tens 26) { dp[i] dp[i - 2]; } } return dp[n]; } };c/0091-decode-ways.c 同样给出 C 语言的自底向上版本并显式处理了n 1与末尾为0的基例int numDecodings(char * s){ int n strlen(s); if (n1) return s[0]!0; int* dp malloc(sizeof(int)*(n1)); dp[n] 1; // 空串视为 1 种 dp[n-1] s[n-1]0?0:1; // 末尾为 0 则非法 for (int in-2; i0; i--) { if (s[i]0) { dp[i] 0; } else if (s[i]1 || s[i]2) { if (s[i]2 s[i1]7) dp[i] dp[i2]; // 如 27 只能拆单 else dp[i] dp[i1] dp[i2]; // 两条分支都合法 } else { dp[i] dp[i1]; // 如 3~9 只能拆单 } } return dp[0]; }6.4 复杂度时间复杂度$O(n)$空间复杂度$O(n)$DP 表长度n 17. 解法四空间优化 DP$O(1)$ 空间7.1 关键观察从自底向上版本可知articles/decode-ways.md 的 Space Optimized 章节dp[i]只依赖dp[i1]和dp[i2]因此无需维护整张表只需两个滚动变量dp1→ 从i 1开始解码的方式数dp2→ 从i 2开始解码的方式数。7.2 算法步骤初始化dp1 1对应dp[len(s)]、dp2 0从右向左迭代s[i] 0→ 当前结果dp 0否则dp dp1若两位数合法再dp dp2每轮结束滚动更新dp2 dp1、dp1 dp返回dp1。Python 实现class Solution: def numDecodings(self, s: str) - int: dp dp2 0 dp1 1 for i in range(len(s) - 1, -1, -1): if s[i] 0: dp 0 else: dp dp1 if i 1 len(s) and ( s[i] 1 or s[i] 2 and s[i 1] in 0123456 ): dp dp2 dp, dp1, dp2 0, dp, dp1 return dp17.3 复杂度时间复杂度$O(n)$空间复杂度$O(1)$仓库 javascript/0091-decode-ways.js 的第三种实现2 Pointer 版本进一步展示了从左向右的滚动指针写法用prev与prevPrev两个变量在单次遍历中完成相同的递推并单独抽出isTwoDigit判断函数var isTwoDigit (s, i) { const [prevChar, curChar] [s[i - 1], s[i]]; const is10 prevChar 1; const is20 prevChar 2 curChar 6; return is10 || is20; };这四种解法在 articles/decode-ways.md 中均配有 Java、C、JavaScript、C#、Go、Kotlin、Swift、Rust 的完整 tab 版本可以按语言习惯对照阅读。8. 常见陷阱与边界情况articles/decode-ways.md 的 Common Pitfalls 章节总结了三个最容易被忽略的坑hints/decode-ways.md 的 Hint 1 与 Hint 4 也分别提示了并非所有两位数合法与前导零非法。8.1 未处理前导零以0开头或无法与前一位配对的0会使整个子串解码数为 0。这是最常见的漏判点# Wrong: 不处理 0 的情况 res dfs(i 1) # Correct: 0 无字母映射返回 0 if s[i] 0: return 0 res dfs(i 1)典型反例s 0→ 0 种s 01→ 0 种s 10→ 1 种只有J1与0不能拆开因为0无法单独解码。8.2 两位数合法性校验错误两位数字只有当数值落在10–26之间才合法。常见的错误是不校验直接累加从而把00、07、30等非法组合计入# Wrong: 允许 00、30 等非法两位数 if i 1 len(s): res dfs(i 2) # Correct: 仅允许 10-26 if i 1 len(s) and (s[i] 1 or (s[i] 2 and s[i 1] 6)): res dfs(i 2)8.3 基例值混淆当i越过字符串末尾整串解码成功时应返回1——表示从起点到这里的这一条路径是 1 种完整解码。若误返回 0所有路径都会被计为 0# Wrong: 返回 0 导致全部计数归零 if i len(s): return 0 # Correct: 到达末尾意味着一条完整解码路径 if i len(s): return 1另外注意自底向上版本中的dp[len(s)] 1正是这一基例在迭代形式下的对应物二者必须保持一致。9. 仓库中的多语言实现索引本题在仓库中属于完成度较高的题目之一README.md 的题解总表中标记0091 - Decode Ways在 C、C、C#、Go、Java、JavaScript、Kotlin、Python、Rust、TypeScript、Swift 等语言下均有实现可对照阅读语言文件Cc/0091-decode-ways.c自底向上显式处理边界Ccpp/0091-decode-ways.cpp自底向上从前向后递推Gogo/0091-decode-ways.go记忆化 制表双版本JavaScriptjavascript/0091-decode-ways.js记忆化、制表、双指针三版本Pythonpython/0091-decode-ways.py记忆化 制表Rustrust/0091-decode-ways.rs记忆化Optioni32缓存TypeScripttypescript/0091-decode-ways.ts自底向上各语言实现共同印证了同一套核心逻辑单数字解码要求非零双数字解码要求落在10–26子问题结果可缓存复用。读者可以选取自己熟悉的语言在本地运行几个代表性用例12→ 2226→ 306→ 010→ 1验证上述四种解法的输出一致性。总结Decode Ways 是掌握一维线性 DP 建模的经典入门题其要点可归纳为建模每个位置只有取一位 / 取两位两种分支递推关系为dfs(i) dfs(i 1) dfs(i 2)但需以合法性为前提收敛朴素递归 $O(2^n)$ 因大量重叠子问题而失效通过记忆化自顶向下或填表自底向上收敛到 $O(n)$ 时间优化利用只依赖后两个位置的特性用两个滚动变量把空间压到 $O(1)$边界前导零、两位数字区间10–26校验、基例返回1三者缺一不可。沿 hints/decode-ways.md 的四个提示顺序思考复杂度目标 → 决策树递推 → 消除重复 → 基例与缓存配合 articles/decode-ways.md 的多语言完整实现与仓库源码交叉验证即可彻底吃透这一经典 DP 问题。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode 91 Decode Ways 解码方式计数：从递归到动态规划的四种递进解法（附多语言源码）
LeetCode 91 Decode Ways 解码方式计数从递归到动态规划的四种递进解法附多语言源码【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode导读本文围绕 LeetCode 第 91 题「Decode Ways」展开讲解如何统计一条仅含数字的字符串可以被映射为字母A–Z对应1–26的所有合法解码方式。文章以仓库内 hints/decode-ways.md 的解题提示为主线完整继承其关于复杂度目标、决策树递推关系、备忘录缓存与边界条件的四个递进式提示并结合 articles/decode-ways.md 的详细推导给出从朴素递归$O(2^n)$到记忆化搜索、自底向上 DP、空间优化 DP$O(n)$ 时间 / $O(1)$ 空间的完整演进路径。读完本文你将掌握该题的递推建模、两种 DP 实现范式以及前导零等边界陷阱的规避方法并能对照仓库中 C、C、Go、Java、JavaScript、Python、Rust、TypeScript 等多语言实现进行交叉验证。1. 问题定义与字母映射规则题目给出一条只包含数字字符的字符串s要求返回所有可能的解码方法总数。映射规则为1→A2→B…26→Z也就是说一个映射值可以是1 位数字1–9也可以是2 位数字10–26。仓库中 cpp/0091-decode-ways.cpp 的文件头注释给出了两个直观示例s 12→ 2 种AB1 2或L12s 226→ 3 种2 26、22 6、2 2 6关键约束来自 articles/decode-ways.md 的 Prerequisites 与递归章节单数字解码s[i]不能为0因为没有任何字母映射到0双数字解码s[i:i2]必须落在10–26区间内字符串中的0只能作为双数字的第二位如10、20出现否则该子串不可解码。2. 复杂度目标以 $O(n)$ 时间和 $O(n)$ 空间为基准hints/decode-ways.md 的开篇提示Recommended Time Space Complexity明确要求目标解法应达到或优于$O(n)$ 时间、$O(n)$ 空间其中n为给定字符串长度。这一目标直接决定了思路走向$O(n)$ 意味着不能枚举全部解码组合那是 $O(2^n)$必须利用子问题的重叠性做动态规划或记忆化搜索。后文四种解法正是围绕如何从 $O(2^n)$ 收敛到 $O(n)$展开的。3. 建模核心决策树与递推关系Hint 1 Hint 23.1 每个位置只有两种选择hints/decode-ways.md 的 Hint 1 指出由于映射值最多 2 位扫描字符串时可以把一个或两个连续数字组合起来探索所有可能的解码路径这本质是一棵决策树。在任意下标i处只有两种选择取一位s[i]要求s[i] ! 0取两位s[i:i2]要求数值落在10–26。3.2 递推关系Hint 2 进一步给出递推骨架从下标i开始解码的方式数等于$$dfs(i) dfs(i 1) dfs(i 2)$$其中dfs(i 1)对应取一位分支dfs(i 2)对应取两位分支。但并不是每次两个分支都合法——前导零、超过26的两位数都构成非法路径这正是后文边界条件的重点。以s 226为例的决策树由 articles/decode-ways.md 的递归直觉推导dfs(0) 226 ├── 取一位 2 → dfs(1) 26 │ ├── 取一位 2 → dfs(2) 6 → 取一位 6 → dfs(3) 1 (2-2-6) │ └── 取两位 26 → dfs(3) 1 (2-26) └── 取两位 22 → dfs(2) 6 → 取一位 6 → dfs(3) 1 (22-6) 合计 34. 解法一朴素递归Brute Force DFS4.1 基例与递归逻辑articles/decode-ways.md 的递归章节给出的算法骨架定义dfs(i) 解码s[i:]的方式数基例i len(s)→ 返回1整串解码完成当前路径计 1 次s[i] 0→ 返回0非法起点递归求和先取一位dfs(i 1)若两位数字合法10–26再加dfs(i 2)从dfs(0)开始。Python 实现与 python/0091-decode-ways.py 中的递归思路一致class Solution: def numDecodings(self, s: str) - int: def dfs(i): if i len(s): return 1 if s[i] 0: return 0 res dfs(i 1) if i len(s) - 1: if (s[i] 1 or (s[i] 2 and s[i 1] 7)): res dfs(i 2) return res return dfs(0)4.2 复杂度$O(2^n)$ 的指数灾难递归每次至多分叉两次最坏情况下如全1串会形成指数级调用树。但注意大量调用携带相同的参数i重复计算同一子问题。时间复杂度$O(2^n)$来自 articles/decode-ways.md 递归章节hints/decode-ways.md 的 Hint 3 也明确指出暴力递归为 $O(2^n)$空间复杂度$O(n)$递归调用栈深度这一版本适合理解递推本质但无法通过大规模测试用例必须消除重复计算。5. 解法二自顶向下 DP记忆化搜索5.1 核心观察子问题重叠hints/decode-ways.md 的 Hint 3 与 Hint 4 给出两条关键指引Hint 3考虑重复调用同参数递归造成的重复工作想办法避免它并思考递归函数的基例Hint 4基例是i越界时返回1当前位为0时返回0使用数组或哈希表缓存递归结果命中缓存直接返回。5.2 算法步骤用字典dp记录dp[i] 解码s[i:]的方式数初始化dp[len(s)] 1空串视为 1 种合法解码对应基例dfs(i)命中缓存直接返回s[i] 0返回0否则计算dfs(i 1)两位数合法时加dfs(i 2)结果存入dp[i]后返回最终调用dfs(0)。Python 实现即 python/0091-decode-ways.py 的 Memoization 版本class Solution: def numDecodings(self, s: str) - int: dp {len(s): 1} def dfs(i): if i in dp: return dp[i] if s[i] 0: return 0 res dfs(i 1) if i 1 len(s) and ( s[i] 1 or s[i] 2 and s[i 1] in 0123456 ): res dfs(i 2) dp[i] res return res return dfs(0)注意两位数的合法性判断有两种等价写法articles/decode-ways.md 中多语言版本均有体现字符比较法s[i] 1 or (s[i] 2 and s[i 1] 7)集合包含法s[i] 1 or s[i] 2 and s[i 1] in 0123456两者都精确限定两位数字在10–26区间以1开头时第二位可为0–9以2开头时第二位只能是0–6。5.3 复杂度时间复杂度$O(n)$——每个下标至多计算一次空间复杂度$O(n)$——缓存字典或数组加递归栈。仓库的 go/0091-decode-ways.go 提供了用切片dp代替哈希表的记忆化实现rust/0091-decode-ways.rs 则用VecOptioni32区分未计算与已缓存状态可作为不同语言惯用写法的参考。6. 解法三自底向上 DPTabulation6.1 反转视角自底向上不再递归而是从后往前构建答案articles/decode-ways.md 的 Bottom-Up 章节dp[i] 解码子串s[i:]的方式数最终答案是dp[0]每个位置只依赖其后1 或 2 个位置天然适合迭代填表。6.2 算法步骤建立 DP 表基例dp[len(s)] 1从i len(s) - 1向左迭代s[i] 0→dp[i] 0否则dp[i] dp[i 1]取一位若两位数合法则再加dp[i 2]返回dp[0]。Python 实现即 python/0091-decode-ways.py 的 Dynamic Programming 版本class Solution: def numDecodings(self, s: str) - int: dp {len(s): 1} for i in range(len(s) - 1, -1, -1): if s[i] 0: dp[i] 0 else: dp[i] dp[i 1] if i 1 len(s) and ( s[i] 1 or s[i] 2 and s[i 1] in 0123456 ): dp[i] dp[i 2] return dp[0]6.3 另一种等价视角从前往后仓库 cpp/0091-decode-ways.cpp 采用从前向后的递推写法递推关系为dp[i] dp[i-1] (若 s[i-1] 是 1~9) dp[i] dp[i-2] (若 s[i-2:i] 是 10~26)class Solution { public: int numDecodings(string s) { if (s[0] 0) { return 0; } int n s.size(); vectorint dp(n 1); dp[0] 1; dp[1] 1; for (int i 2; i n; i) { int ones stoi(s.substr(i - 1, 1)); if (ones 1 ones 9) { dp[i] dp[i - 1]; } int tens stoi(s.substr(i - 2, 2)); if (tens 10 tens 26) { dp[i] dp[i - 2]; } } return dp[n]; } };c/0091-decode-ways.c 同样给出 C 语言的自底向上版本并显式处理了n 1与末尾为0的基例int numDecodings(char * s){ int n strlen(s); if (n1) return s[0]!0; int* dp malloc(sizeof(int)*(n1)); dp[n] 1; // 空串视为 1 种 dp[n-1] s[n-1]0?0:1; // 末尾为 0 则非法 for (int in-2; i0; i--) { if (s[i]0) { dp[i] 0; } else if (s[i]1 || s[i]2) { if (s[i]2 s[i1]7) dp[i] dp[i2]; // 如 27 只能拆单 else dp[i] dp[i1] dp[i2]; // 两条分支都合法 } else { dp[i] dp[i1]; // 如 3~9 只能拆单 } } return dp[0]; }6.4 复杂度时间复杂度$O(n)$空间复杂度$O(n)$DP 表长度n 17. 解法四空间优化 DP$O(1)$ 空间7.1 关键观察从自底向上版本可知articles/decode-ways.md 的 Space Optimized 章节dp[i]只依赖dp[i1]和dp[i2]因此无需维护整张表只需两个滚动变量dp1→ 从i 1开始解码的方式数dp2→ 从i 2开始解码的方式数。7.2 算法步骤初始化dp1 1对应dp[len(s)]、dp2 0从右向左迭代s[i] 0→ 当前结果dp 0否则dp dp1若两位数合法再dp dp2每轮结束滚动更新dp2 dp1、dp1 dp返回dp1。Python 实现class Solution: def numDecodings(self, s: str) - int: dp dp2 0 dp1 1 for i in range(len(s) - 1, -1, -1): if s[i] 0: dp 0 else: dp dp1 if i 1 len(s) and ( s[i] 1 or s[i] 2 and s[i 1] in 0123456 ): dp dp2 dp, dp1, dp2 0, dp, dp1 return dp17.3 复杂度时间复杂度$O(n)$空间复杂度$O(1)$仓库 javascript/0091-decode-ways.js 的第三种实现2 Pointer 版本进一步展示了从左向右的滚动指针写法用prev与prevPrev两个变量在单次遍历中完成相同的递推并单独抽出isTwoDigit判断函数var isTwoDigit (s, i) { const [prevChar, curChar] [s[i - 1], s[i]]; const is10 prevChar 1; const is20 prevChar 2 curChar 6; return is10 || is20; };这四种解法在 articles/decode-ways.md 中均配有 Java、C、JavaScript、C#、Go、Kotlin、Swift、Rust 的完整 tab 版本可以按语言习惯对照阅读。8. 常见陷阱与边界情况articles/decode-ways.md 的 Common Pitfalls 章节总结了三个最容易被忽略的坑hints/decode-ways.md 的 Hint 1 与 Hint 4 也分别提示了并非所有两位数合法与前导零非法。8.1 未处理前导零以0开头或无法与前一位配对的0会使整个子串解码数为 0。这是最常见的漏判点# Wrong: 不处理 0 的情况 res dfs(i 1) # Correct: 0 无字母映射返回 0 if s[i] 0: return 0 res dfs(i 1)典型反例s 0→ 0 种s 01→ 0 种s 10→ 1 种只有J1与0不能拆开因为0无法单独解码。8.2 两位数合法性校验错误两位数字只有当数值落在10–26之间才合法。常见的错误是不校验直接累加从而把00、07、30等非法组合计入# Wrong: 允许 00、30 等非法两位数 if i 1 len(s): res dfs(i 2) # Correct: 仅允许 10-26 if i 1 len(s) and (s[i] 1 or (s[i] 2 and s[i 1] 6)): res dfs(i 2)8.3 基例值混淆当i越过字符串末尾整串解码成功时应返回1——表示从起点到这里的这一条路径是 1 种完整解码。若误返回 0所有路径都会被计为 0# Wrong: 返回 0 导致全部计数归零 if i len(s): return 0 # Correct: 到达末尾意味着一条完整解码路径 if i len(s): return 1另外注意自底向上版本中的dp[len(s)] 1正是这一基例在迭代形式下的对应物二者必须保持一致。9. 仓库中的多语言实现索引本题在仓库中属于完成度较高的题目之一README.md 的题解总表中标记0091 - Decode Ways在 C、C、C#、Go、Java、JavaScript、Kotlin、Python、Rust、TypeScript、Swift 等语言下均有实现可对照阅读语言文件Cc/0091-decode-ways.c自底向上显式处理边界Ccpp/0091-decode-ways.cpp自底向上从前向后递推Gogo/0091-decode-ways.go记忆化 制表双版本JavaScriptjavascript/0091-decode-ways.js记忆化、制表、双指针三版本Pythonpython/0091-decode-ways.py记忆化 制表Rustrust/0091-decode-ways.rs记忆化Optioni32缓存TypeScripttypescript/0091-decode-ways.ts自底向上各语言实现共同印证了同一套核心逻辑单数字解码要求非零双数字解码要求落在10–26子问题结果可缓存复用。读者可以选取自己熟悉的语言在本地运行几个代表性用例12→ 2226→ 306→ 010→ 1验证上述四种解法的输出一致性。总结Decode Ways 是掌握一维线性 DP 建模的经典入门题其要点可归纳为建模每个位置只有取一位 / 取两位两种分支递推关系为dfs(i) dfs(i 1) dfs(i 2)但需以合法性为前提收敛朴素递归 $O(2^n)$ 因大量重叠子问题而失效通过记忆化自顶向下或填表自底向上收敛到 $O(n)$ 时间优化利用只依赖后两个位置的特性用两个滚动变量把空间压到 $O(1)$边界前导零、两位数字区间10–26校验、基例返回1三者缺一不可。沿 hints/decode-ways.md 的四个提示顺序思考复杂度目标 → 决策树递推 → 消除重复 → 基例与缓存配合 articles/decode-ways.md 的多语言完整实现与仓库源码交叉验证即可彻底吃透这一经典 DP 问题。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考