原题链接:
https://leetcode.cn/problems/decode-ways/solutions/730937/gong-shui-san-xie-gen-ju-shu-ju-fan-wei-ug3dd/
完成情况:
解题思路:
这段代码是一个解码方法的函数,目的是计算字符串s有多少种解码方法。具体解释如下:
- 首先,将字符串s的长度存储在变量n中。
- 然后,在字符串s的前面加上一个空格,这样方便后续处理。
- 将字符串s转换为字符数组cs。
- 创建一个长度为n+1的整型数组f,用于存储解码方法的数量。
- 初始化f[0]为1,表示空字符串有一种解码方法。
- 使用for循环遍历字符串s的每个字符:
- 定义a为当前位置的数字,b为当前位置与前一位置组成的两位数字。
- 如果a在1到9之间,则f[i]可以由f[i-1]转移过来。
- 如果b在10到26之间,则f[i]可以由f[i-2]或者f[i-1]和f[i-2]共同转移过来。
- 最终返回f[n],即字符串s的解码方法数量。
参考代码:
_91解码方法
package leetcode板块;
public class _91解码方法 {
/**
* 一条包含字母 A-Z 的消息通过以下映射进行了 编码 :
* 'A' -> "1"
* 'B' -> "2"
* ...
* 'Z' -> "26"
*
* @param s
* @return 返回所有可能的解码集合
*/
// public int numDecodings(String s) {
// int n = s.length();
// //s = " " + s;
// char[] chars = s.toCharArray();
// int[] dp_findNums = new int[n + 1];
// dp_findNums[0] = 1;
// for (int i = 1; i <= n; i++) {
// // a : 代表「当前位置」单独形成 item
// // b : 代表「当前位置」与「前一位置」共同形成 item
// int aloneItem = chars[i] - '0', uniItem = (chars[i - 1] - '0') * 10 + (chars[i] - '0');
// // 如果 a 属于有效值,那么 f[i] 可以由 f[i - 1] 转移过来
// if (1 <= aloneItem && aloneItem <= 9) dp_findNums[i] = dp_findNums[i - 1];
// // 如果 b 属于有效值,那么 f[i] 可以由 f[i - 2] 或者 f[i - 1] & f[i - 2] 转移过来
// if (10 <= uniItem && uniItem <= 26) dp_findNums[i] += dp_findNums[i - 2];
// }
// return dp_findNums[n];
// }
public int numDecodings(String s) {
//每个s里面的独立元素,至少要取一个,至多也只能取两个
//然后一个元素,必然也不能以0开头,所以遇到有0的,就只能跟前面一个人元素进行结合
int n = s.length();
s = " "+s;
char [] chars = s.toCharArray();
int [] dp_findNums = new int[n+1];
dp_findNums[0] = 1;
for (int i = 1;i<=n;i++){
// 要区分两种情况,一种就是单独一个元素形成一个item -> aloneItem
// 另一种就是与别人结合,形成一个item -> uniItem
int aloneItem = chars[i] - '0',uniItem = (chars[i-1] - '0')*10 + (chars[i] - '0');
//分别记录 aloneItem 与 uniItem的有效性,同时迭代当前情况的累计次数
if (1<= aloneItem && aloneItem <= 9) dp_findNums[i] = dp_findNums[i-1]; //说明是正常情况,逐一都是一个值
if (10 <= uniItem && uniItem <= 26) dp_findNums[i] += dp_findNums[i-2]; //说明可以与前面的数值进行结合,产生一个新的解
}
return dp_findNums[s.length()];
}
}
_91解码方法_三数组实现往复覆盖
package leetcode板块;
public class _91解码方法_三数组实现往复覆盖 {
/**
*
* @param s
* @return
*/
public int numDecodings(String s){
int n = s.length();
s = " "+s;
char [] chars = s.toCharArray();
char [] charsArray = s.toCharArray();
int [] dp_findNums = new int[3];
dp_findNums[0] = 1;
for (int i = 1;i<=n;i++){
dp_findNums[i % 3] = 0;
int aloneItem = chars[i] - '0',uniItem = (chars[i-1] - '0')*10 + (chars[i] - '0');
if (1 <= aloneItem && aloneItem <= 9) dp_findNums[i % 3] = dp_findNums[(i-1) % 3];
if (10 <= uniItem && uniItem <= 26) dp_findNums[i % 3] = dp_findNums[(i-2) % 3];
}
return dp_findNums[n % 3];
}
}