CS-Notes 剑指 Offer 46把数字翻译成字符串——用动态规划计算数字串的解码方案数【免费下载链接】CS-Notes:books: 技术面试必备基础知识、Leetcode、计算机操作系统、计算机网络、系统设计项目地址: https://gitcode.com/GitHub_Trending/cs/CS-Notes在 CS-Notes 仓库中46. 把数字翻译成字符串 收录的是剑指 Offer 系列里一道经典的动态规划题给定一个数字串按照 1→a、2→b … 26→z 的规则计算它有多少种不同的翻译方法。本篇基于原文档的题目描述与 Java 解法结合 Leetcode 题解 - 动态规划 中对同一问题的收录完整讲清状态定义、转移方程、0 字符的边界处理以及空间优化思路读完后可独立实现并手动验证该算法在任意数字串上的正确性。题目描述原文档给出的完整题目如下给定一个数字按照如下规则翻译成字符串1 翻译成a2 翻译成b … 26 翻译成z。一个数字有多种翻译可能例如 12258 一共有 5 种分别是 abbehlbehavehabyhlyh。实现一个函数用来计算一个数字有多少种不同的翻译方法。这道题的关键在于多种翻译可能每一位数字既可以单独翻译成字母也可以和相邻的两位组合翻译当这两位组成的数在 1~26 范围内时。这正是分割整数构成字母字符串这一类划分计数问题的典型形态——Leetcode 题解 - 动态规划 一文将该题归入分割整数章节的分割整数构成字母字符串小节对应 LeetCode 91. Decode Ways解法与本文完全一致。解题思路从递归到动态规划先把问题翻译成选择语言扫描数字串每个位置有两种可选动作——单独翻译当前位当前位不为 00 不能单独映射成字母时方案数继承前一位的累计方案数与上一位合并翻译取末尾两位组成的整数当它落在 1~26 之间且十位不是 0即 10~26时方案数继承前两位的累计方案数。两种动作互不排斥方案数相加。若用f(i)表示数字串前i位共有多少种翻译方法状态转移方程为f(i) f(i - 1) 当 s[i-1] ! 0 时 f(i - 2) 当 10 s[i-2..i-1] 26 时 f(0) 1 空串记 1 种作为计数基例 f(1) s[0] 0 ? 0 : 1这正是递归保存子问题解的动态规划f(i)依赖的f(i-1)、f(i-2)只会被计算一次避免暴力枚举全部切分方式的指数级重复。完整实现原文档代码原文档给出的解法如下这里保留原始结构并补充逐行注释public int numDecodings(String s) { if (s null || s.length() 0) return 0; // 空输入没有合法翻译 int n s.length(); int[] dp new int[n 1]; // dp[i]前 i 个字符的翻译方法数 dp[0] 1; // 空串作为计数基例保证 dp[2] 可由 dp[0] 累加 dp[1] s.charAt(0) 0 ? 0 : 1; // 首字符是 0 无法翻译 for (int i 2; i n; i) { // 动作一单独翻译第 i 个字符下标 i-1 int one Integer.valueOf(s.substring(i - 1, i)); if (one ! 0) dp[i] dp[i - 1]; // 动作二与第 i-1 个字符合并翻译 if (s.charAt(i - 2) 0) continue; // 十位是 0 时 0x 不构成 1~26跳过 int two Integer.valueOf(s.substring(i - 2, i)); if (two 26) dp[i] dp[i - 2]; // 合并位合法10~26则叠加前两位的方案数 } return dp[n]; }实现中有三个细节值得特别注意dp[0] 1的含义它不是空串有 1 种翻译的语义结论而是让转移方程dp[i] dp[i-2]在i 2时能够正确累加前两位合并翻译这条路径的计数基例。s.charAt(i - 2) 0的提前跳过当十位为 0 时两位组合形如 01~09都不在 1~26 范围内合并动作必然非法直接continue可以避免多余的Integer.valueOf。这与单独动作中one ! 0的判断共同构成了对 0 的完整防御。合并合法性判据是two 26由于十位已排除 0进入该分支时two必然 ≥ 10因此只需上界判断。用原文档示例手动验证12258 的 5 种翻译按上述状态表逐位推进12258i前缀动作一单独动作二合并dp[i]0——1111≠0 → dp[0]1无12122≠0 → dp[1]112≤26 → dp[0]1231222≠0 → dp[2]222≤26 → dp[1]13412255≠0 → dp[3]325≤26 → dp[2]255122588≠0 → dp[4]55826 非法5最终dp[5] 5与题目描述中 abbeh、lbeh、aveh、abyh、lyh 五种翻译一致。再用几组典型输入检验边界行为以下结果均为按原文档代码逻辑逐步推演的输出输入输出说明2263b b f、b v、b f 三种切分00首字符为 0无合法翻译30030 中 0 无法单独翻译且 30 26101只能整体翻译为 j262z 或 b z 两种27127 26只能拆成 b a060首字符 0 直接导致整体非法可以看到0 的处理是该题正确性的分水岭只要前缀中出现无法归属的 0后续所有状态都会因为dp值归零而保持为 0。复杂度与空间优化原实现使用长度为n1的数组滚动时间复杂度O(n)每一位只做常数次取子串与比较空间复杂度O(n)。从源码结构看dp[i]只依赖dp[i-1]和dp[i-2]两个前驱状态因此可以用两个变量代替数组把空间压到 O(1)public int numDecodings(String s) { if (s null || s.length() 0) return 0; int prev2 1; // 等价于 dp[i-2]初始 dp[0] int prev1 s.charAt(0) 0 ? 0 : 1; // 等价于 dp[i-1]初始 dp[1] if (s.length() 1) return prev1; for (int i 2; i s.length(); i) { int cur 0; if (s.charAt(i - 1) ! 0) cur prev1; // 单独翻译当前位 if (s.charAt(i - 2) ! 0) { int two (s.charAt(i - 2) - 0) * 10 (s.charAt(i - 1) - 0); if (two 26) cur prev2; // 与上一位合并翻译 } prev2 prev1; prev1 cur; } return prev1; }这一写法与原文档算法逐项等价只是将Integer.valueOf(s.substring(...))换成了直接的数字位运算去掉了每次循环创建子串的小开销面试白板场景下更顺手。需要注意原文档方案返回类型为int当数字串较长时方案数会超过 2^31 - 1 造成溢出若题目要求精确计数可改用long或取模。延伸与 LeetCode 91 Decode Ways 的关系同一份numDecodings解法在仓库中还收录于 Leetcode 题解 - 动态规划 的分割整数 → 分割整数构成字母字符串小节LeetCode 91. Decode Ways, Medium题面描述为Given encoded message 12, it could be decoded as AB (1 2) or L (12).两题建模完全相同区别仅在输入形式整数串 vs 字符串。因此掌握本文的状态定义、转移方程和 0 的三类边界首字符 0、中间 0x、超过 26 的组合即可同时覆盖剑指 Offer 46 与 LeetCode 91 两个变体。该题在 剑指 Offer 题解 - 目录 中归入其它分类可与同分类的 19. 正则表达式匹配、67. 把字符串转换成整数 串成一条字符串 递推的练习线。【免费下载链接】CS-Notes:books: 技术面试必备基础知识、Leetcode、计算机操作系统、计算机网络、系统设计项目地址: https://gitcode.com/GitHub_Trending/cs/CS-Notes创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考