剑指offer-70、把数字翻译成为字符串
<h2 id="题描述">题⽬描述</h2><p>有⼀种将字⺟编码成数字的⽅式：'a'->1, 'b->2', ... , 'z->26'。</p>
<p>现在给⼀串数字，返回有多少种可能的译码结果</p>
<p>示例1<br>
输⼊："12"<br>
返回值：2<br>
说明：2种可能的译码结果（”ab” 或”l”）</p>
<p>示例2<br>
输⼊："31717126241541717"<br>
返回值：192<br>
说明：192种可能的译码结果</p>
<p>仔细观察，就会发现上⾯的编码从 1 到 26，也就是可能⼀次译码使⽤是 1 位，也可能是⼀次译码⽤了 2位，⽐如 12 ，可以第⼀次⽤ 1，2 分开分别译码，也可以把 1，2 合并起来进⾏译码。</p>
<h2 id="思路及解法">思路及解法</h2>
<h3 id="暴力递归">暴力递归</h3>
<p>假设⼀个字符是S，第⼀次拆解就有两种情况，然后分别对后⾯的部分分别译码，使⽤递归即可：</p>
<p><img src="https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202504201124096.png" alt="" loading="lazy"></p>
<pre><code class="language-java">public class Solution46 {
public int solve (String nums) {
return recursion(nums.toCharArray(), 0);
}
public int recursion(char[] nums, int start){
if(start == nums.length){
return 1;
}
if(nums == '0')
return 0;
// 使⽤⼀位字符译码
int count1 = recursion(nums,start+1);
int count2 = 0;
// 符合两位字符的译码
if((start < nums.length-1) && (nums == '1' || (nums == '2' &&nums <= '6'))){
count2 = recursion(nums,start+2);
}
return count1 + count2;
}
}
</code></pre>
<p>但是上⾯的代码时间复杂度太⾼了，只要字符稍微⻓⼀点，运⾏时间就容易超过限制了：</p>
<h3 id="记忆化递归">记忆化递归</h3>
<p>为了避免重复计算子问题，我们使用一个备忘录（<code>memo</code>）来存储已经计算过的结果。</p>
<pre><code class="language-java">class Solution {
public int numDecodings(String s) {
if (s == null || s.length() == 0) return 0;
// 备忘录，初始化为-1表示未计算
Integer[] memo = new Integer;
return dfs(s, 0, memo);
}
private int dfs(String s, int index, Integer[] memo) {
// 基准情况1：成功解码到末尾，算作一种有效方法
if (index == s.length()) {
return 1;
}
// 基准情况2：当前字符是'0'，无法解码，此路径无效
if (s.charAt(index) == '0') {
return 0;
}
// 如果当前子问题已经计算过，直接返回结果
if (memo != null) {
return memo;
}
int ways = 0;
// 选择1：解码当前1位数字
ways += dfs(s, index + 1, memo);
// 选择2：如果存在下一位，并且当前两位数字在10-26之间，则解码当前2位数字
if (index + 1 < s.length()) {
int twoDigits = (s.charAt(index) - '0') * 10 + (s.charAt(index + 1) - '0');
if (twoDigits >= 10 && twoDigits <= 26) {
ways += dfs(s, index + 2, memo);
}
}
// 将结果存入备忘录
memo = ways;
return ways;
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n)，每个子问题最多被计算一次。</li>
<li><strong>空间复杂度</strong>：O(n)，递归栈的深度和备忘录的空间</li>
</ul>
<h3 id="动态规划">动态规划</h3>
<p>将过程逆推，要想求得当前的字符串的译码类型，其实有两种，最后⼀个单独翻译，另外⼀种是倒数最后两个字符合起来翻译，这两者之和就是我们所要求的结果。</p>
<p><img src="https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202504201126335.png" alt="" loading="lazy"></p>
<p>⽽要求前⾯的值，需要求更前⾯的值，最后⼀定会求得⼀个字符和两个字符的结果。其实这就是动态规划⾥⾯说的状态变化。递归其实就是逆推，这样会导致很多重复的计算。动态规划,则是从⼩数值计算到⼤数值。</p>
<p>既然我们知道是动态规划，定义 dp 为数字串从左到右第i个数字结尾的当前数字串所拥有的翻译⽅法数，接着就需要找出状态转移⽅程：</p>
<ul>
<li>如果 i=0 , dp=1</li>
<li>否则
<ul>
<li>如果nums=0，说明需要和前⾯⼀个字符⼀起翻译
<ul>
<li>如果i == 1，以10或者20开头， dp = 1</li>
<li>否则，数字串中存在10或者20的情况下，当前译码数等于后退两步的译码数， dp =dp;</li>
</ul>
</li>
<li>否则，在符合字符范围内， dp=dp+dp</li>
</ul>
</li>
</ul>
<pre><code class="language-java">class Solution {
public int numDecodings(String s) {
if (s == null || s.length() == 0 || s.charAt(0) == '0') {
return 0; // 处理空串或以'0'开头的无效情况
}
int n = s.length();
int[] dp = new int;
// 初始化
dp = 1; // 空字符串有一种解码方式（解码为空）
dp = 1; // 第一个字符只要不是'0'（前面已判断），就有1种解码方式
for (int i = 2; i <= n; i++) {
int oneDigit = s.charAt(i - 1) - '0';// 看最后一个字符（1位数字）
int twoDigits = (s.charAt(i - 2) - '0') * 10 + oneDigit; // 看最后两个字符（2位数字）
// 情况1：最后一个字符可以单独解码（必须是1-9）
if (oneDigit >= 1 && oneDigit <= 9) {
dp += dp;
}
// 情况2：最后两个字符可以组合解码（必须是10-26）
if (twoDigits >= 10 && twoDigits <= 26) {
dp += dp;
}
}
return dp;
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n)，需要遍历整个字符串一次。</li>
<li><strong>空间复杂度</strong>：O(n)，用于存储 <code>dp</code>数组。</li>
</ul>
<h3 id="空间优化动态规划推荐">空间优化动态规划（推荐）</h3>
<p>观察上面的代码可以发现，计算 <code>dp</code>时只依赖于 <code>dp</code>和 <code>dp</code>。因此，我们可以不用维护整个数组，只用两个变量来滚动记录之前的状态即可，从而将空间复杂度优化到常数级别。</p>
<pre><code class="language-java">class Solution {
public int numDecodings(String s) {
if (s == null || s.length() == 0 || s.charAt(0) == '0') {
return 0;
}
int n = s.length();
// 使用变量替代dp数组
int prevPrev = 1; // 对应于 dp，初始化为dp=1
int prev = 1; // 对应于 dp，初始化为dp=1
for (int i = 2; i <= n; i++) {
int current = 0;
int oneDigit = s.charAt(i - 1) - '0';
int twoDigits = (s.charAt(i - 2) - '0') * 10 + oneDigit;
// 情况1：单独解码最后一个字符
if (oneDigit >= 1 && oneDigit <= 9) {
current += prev; // 相当于 dp += dp
}
// 情况2：组合解码最后两个字符
if (twoDigits >= 10 && twoDigits <= 26) {
current += prevPrev; // 相当于 dp += dp
}
// 滚动更新变量，为下一次迭代做准备
prevPrev = prev;
prev = current;
}
return prev;
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n)。</li>
<li><strong>空间复杂度</strong>：O(1)，只使用了固定数量的变量</li>
</ul>
</div>
<div id="MySignature" role="contentinfo">
<p>本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top</p><br><br>
来源：https://www.cnblogs.com/sevencoding/p/19526157
頁:
[1]