1.题目描述
有一种将字母编码成数字的方式:'a'->1, 'b->2', ... , 'z->26'。
现在给一串数字,返回有多少种可能的译码结果
数据范围:字符串长度满足 0<n≤900<n≤90
进阶:空间复杂度 O(n)O(n),时间复杂度 O(n)O(n)
示例1
输入:
"12"返回值:
2说明:
2种可能的译码结果(”ab” 或”l”)示例2
输入:
"31717126241541717"返回值:
192说明:
192种可能的译码结果
2.解题思路
动态规划dp数组的含义:dp[i]表示以nums[i]为结尾的子串所能翻译的可能结果种类数;
以num = "1234"为例,因为第一位数字为1不是0,所以初始化dp[0]=1;
接下来对于2,3,4的遍历,每一次都要统计当前遍历的数字以及它和前一位数字的组合,遍历3时,因为它为3,且和前一个数字组合为23,都满足[1,26]范围,所以cnt = 2,那么当前dp[i] = dp[i-1] + dp[i-2],可以理解为:dp[i-1]就是只将当前位数字进行翻译成字母,剩下i-1位为一个整体,这种方案数就有dp[i-1]种;dp[i-2]就是将当前位数字和它的前一位进行组合后翻译成字母,剩下i-2位为一个整体,这种方案数就有dp[i-2]种;因此dp[i]是dp[i-1]+dp[i-2]的结果。如果cnt = 1,则dp[i] = dp[i-1]就无法再通过组合当前字符与前一个字符获得结果。
3.代码实现
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
* 解码
* @param nums string字符串 数字串
* @return int整型
*/
public int solve (String nums) {
// write code here
int n = nums.length();
//初始化
int[] dp = new int[n];
if (nums.charAt(0) - '0' == 0) {
dp[0] = 0;
} else {
dp[0] = 1;
}
for (int i = 1; i < n; i++) {
int cnt = 0;
int cur = nums.charAt(i) - '0';
if (cur != 0) {
cnt += 1;
}
int pre = Integer.parseInt(nums.substring(i - 1, i + 1));
if (pre >= 1 && pre <= 26 && cur != pre) {
cnt += 1;
}
if (i == 1 || cnt == 0) {
dp[i] = cnt;
} else if (cnt == 1){
dp[i] = dp[i-1];
} else {
dp[i] = dp[i-1] + dp[i-2];
}
}
return dp[n - 1];
}
}
标签:pre,cnt,数字,nums,int,字符串,翻译成,BM69,dp
From: https://blog.csdn.net/cqjnovo/article/details/141127187