题目

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

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

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

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

示例1

输入：

"12"

返回值：

2

说明：

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

示例2

输入：

"31717126241541717"

返回值：

192

说明：

192种可能的译码结果

---

代码

import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** 解码* @param nums string字符串 数字串* @return int整型*/public int solve (String nums) {int n = nums.length();//将字符串转化为字符数组char[] s = nums.toCharArray();//1.创建dp表int[] dp = new int[n];//2.初始化//2.1.处理第一种情况if(s[0] != '0') {dp[0] = 1;}//处理边界情况if(n == 1) {return dp[0];}//2.2.处理第二种情况//单独处理2个位置if(s[0] != '0' && s[1] != '0') {dp[1] += 1;}//2个位置一起处理int t = (s[0] - '0') * 10 + (s[1] - '0');if(t >= 10 && t <= 26) {dp[1] += 1;}//3.填表for(int i = 2; i < n; i++) {//3.1.单独解码的情况if(s[i] != '0') {dp[i] += dp[i- 1];}//3.2.同时解码2个位置的情况int tt = (s[i- 1] - '0') * 10 + (s[i] - '0');if(tt >= 10 && tt <= 26) {dp[i] += dp[i- 2];}}//4.返回值return dp[n - 1];}
}