描述

有一种将字母编码成数字的方式：'a'->1, 'b->2', ... , 'z->26'。

现在给一串数字，返回有多少种可能的译码结果

数据范围：字符串长度满足 0<n≤90

进阶：空间复杂度 O(n)，时间复杂度 O(n)

示例1

输入：

"12"

返回值：

2

说明：

2种可能的译码结果（”ab” 或”l”）  

示例2

输入：

"31717126241541717"

返回值：

192

说明：

192种可能的译码结果  

思路分析：

该题可以使用动态规划的方法来解决，其实和跳台阶的方法很类似，里面的编码组合，有一位数和两位数（10~26），可以通过限制条件来解决该问题

1. 边界条件检查：
   • 如果输入字符串nums为空或第一个字符是'0'，则直接返回0，因为无法形成有效的两位数映射。
2. 初始化动态规划数组：
   • 创建一个整型数组dp，长度为nums的长度。dp[i]表示nums的前i+1个字符可以表示的不同字母组合的数量。
   • 初始化dp[0] = 1，表示空字符串或单个字符（非'0'）可以表示1种组合（即它本身）。
3. 动态规划过程：
   • 遍历字符串nums的每个字符（从索引1开始，因为dp[0]已经初始化）。
   • 对于每个字符，首先检查它是否不是'0'。如果不是'0'，则至少可以保持与前一个字符相同的组合数（即dp[i] = dp[i-1]）。
   • 接着，检查当前字符与前一个字符组成的两位数（num）是否在10到26之间。如果是，则需要根据当前位置更新dp[i]的值。
     • 如果这是第二个字符（即i == 1），则直接增加1到dp[i]，因为此时只能形成一个新的两位数组合。
     • 如果不是第二个字符，则增加dp[i-2]到dp[i]。这是因为，如果当前两位数有效，那么它可以与前面的所有有效组合结合，形成新的组合。由于我们已经计算了dp[i-2]，它表示前i-1个字符可以形成的组合数，因此我们可以直接将其加到dp[i]上。
4. 返回结果：
   • 最后，返回dp[nums.length()-1]，即整个字符串nums可以表示的不同字母组合的总数。

代码：

java">import java.util.*;public class Solution {/*** 解码* @param nums string字符串 数字串* @return int整型*/public int solve (String nums) {if(nums.length()==0||nums.charAt(0)=='0'){return 0;}//定义一个存放组合状态的数组int[] dp=new int[nums.length()];dp[0]=1;for(int i=1;i<dp.length;i++){if(nums.charAt(i)!='0'){dp[i]=dp[i-1];}//处理两位数区间在10~26之间的情况int num=(nums.charAt(i-1)-'0')*10+(nums.charAt(i)-'0');if(num>=10&&num<=26){if(i==1){dp[i]+=1;}else{dp[i]+=dp[i-2];}}}return dp[nums.length()-1];}
}