AlgoPressAppearance
0091-解码方法
https://leetcode.cn/problems/decode-ways
一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：
'A' -> 1
'B' -> 2
...
'Z' -> 26
要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"11106" 可以映射为：
"AAJF" ，将消息分组为 (1 1 10 6)
"KJF" ，将消息分组为 (11 10 6)
注意，消息不能分组为 (1 11 06) ，因为 "06" 不能映射为 "F" ，这是由于 "6" 和 "06" 在映射中并不等价。
给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。
题目数据保证答案肯定是一个 32 位 的整数。
示例 1：
输入：s = "12"
输出：2
解释：它可以解码为 "AB"（1 2）或者 "L"（12）。
示例 2：
输入：s = "226"
输出：3
解释：它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
示例 3：
输入：s = "0"
输出：0
解释：没有字符映射到以 0 开头的数字。
含有 0 的有效映射是 'J' -> "10" 和 'T'-> "20" 。
由于没有字符，因此没有有效的方法对此进行解码，因为所有数字都需要映射。
示例 4：
输入：s = "06"
输出：0
解释："06" 不能映射到 "F" ，因为字符串含有前导 0（"6" 和 "06" 在映射中并不等价）。
提示：
1 <= s.length <= 100
s 只包含数字，并且可能包含前导零。
基本思路
动态规划，从前往后开始译码
dp[i] 记录到当前位置译码的可能性
因为s只包含数字 dp[0] = 1
dp[i] = dp[i-1] (前面译码的可能性，本字符单独译码1次) + s[i-1]s[i] 是否可以译码
参考代码1:错误示范
主要是 2101 这个后置性的考虑推翻了前面的思路，具体思路是 到第三位 0 的时候， 就不能复制 dp[i-1] 的编码路线 即 每一位数，有两种编码方式 1 位数，就复制 dp[i-1], 两位数 就复制 += dp[i-2] ，如果两种条件都不满则，就为 0
csharp
//错误示范
public class Solution {
public int NumDecodings(string s) {
int[] dp = new int[s.Length];
dp[0] = 1;
if(s[0] == '0') {
return 0;
}
for(int i=1; i<s.Length; i++){
//check behind
if(s[i] == '0'){
if(s[i-1] == '1' || s[i-1] == '2'){
dp[i] = dp[i-1];
}
else{
return 0;
}
}
else if(s[i-1] == '1' || s[i-1] == '2' && s[i] <= '6'){
dp[i] = dp[i-1]+1;
}
else{
dp[i] = dp[i-1];
}
}
return dp[s.Length-1];
}
}
参考代码2：官方解法 注意 s[i] 有移位表示
https://leetcode.cn/problems/decode-ways/solution/jie-ma-fang-fa-by-leetcode-solution-p8np/
csharp
//官方解法 注意 s[i] 有移位表示
public class Solution {
public int NumDecodings(string s) {
int n = s.Length;
int[] dp = new int[n+1];
dp[0] = 1;
// i-1, i-2
for(int i=1; i<=n; i++){
if(s[i-1] != '0'){ //当前字符不是 0
dp[i] = dp[i-1];
}
if(i > 1 && s[i-2] != '0' && Convert.ToInt32(s[i-2].ToString()+s[i-1].ToString()) <= 26 ){
dp[i] += dp[i-2];
}
}
return dp[n];
}
}
参考代码2 根据官方解码，s[i] 无移位
代码理解： dp[i] 表示到该处可能的编码个数
循环到 dp[i]时, dp[i] 初始位 0
s[i] != '0' 说明，本字符和一编码，dp[i] = dp[i-1] ，表示此处编码的方法和前面一样多
下面考虑两位数的情况
当 s[i-1]s[i] 组合起来的时候，且s[i-1]!='0' 小于 26，说明前两位又可以编码，那么这时候编码的方法就是 dp[i-2] 在加上 dp[i], 这一步需要好好理解
当上面两个条件都不满足，说明 dp[i] = 0,无法编码了
演示 2101 :
dp[0] = 1 // 2编码
dp[1] = 2 // 2 1 , 21
dp[2] = 1 // 会判断是否为0，是为0，则 dp[i-1] 不算， 判断两位数 10 则 拷贝 dp[i-2] 即 dp[0]
dp[3] = 1 // 复制dp[i-1] 且 s[i-1] == "0"，所以两位数不算
csharp
public class Solution {
public int NumDecodings(string s) {
int[] dp = new int[s.Length];
dp[0] = s[0] == '0' ? 0 : 1;
for(int i=1; i<s.Length; i++){
//如果当前不等于0，那么本位可以单独编一个码，整个编码方式 = dp[i-1]
if(s[i] != '0'){
dp[i] = dp[i-1];
}
if(s[i-1] != '0' && Convert.ToInt32(s[i-1].ToString()+s[i].ToString()) <= 26){
if(i>=2){
dp[i] += dp[i-2];
}
else{
dp[i] += 1;
}
}
}
return dp[s.Length-1];
}
}
复习:20220520
csharp
public class Solution {
public int NumDecodings(string s) {
//第一个字符为0，就直接退出
if(s[0] == '0'){
return 0;
}
int[] dp = new int[s.Length]; //dp表示位置i的编码方法数
dp[0] = 1;
for(int i=1; i<s.Length; i++){
if(s[i] != '0'){ //正常编码
dp[i] = dp[i-1];
}
//取出最后两位看是否在 10 - 26 之间
int n = Convert.ToInt32(s[i-1].ToString() + s[i].ToString());
if(n >=10 && n <=26){
if(i>=2){
dp[i] += dp[i-2];
}
else{
dp[i] += 1;
}
}
}
return dp[s.Length-1];
}
}
复习:20220701
csharp
public class Solution {
public int NumDecodings(string s) {
if(s[0] == '0'){
return 0;
}
int n = s.Length;
int[] dp = new int[n];
dp[0] = 1; //第一个字符1中编码
for(int i=1; i<s.Length; i++){
//如果当前位置不是1，则可以单独编码，复用前面dp[i-1]的编码方式
if(s[i] != '0'){
dp[i] = dp[i-1];
}
//如果i>=1则可以计算两位
int number = Convert.ToInt32(s.Substring(i-1,2));
if(number >= 10 && number <= 26){
if(i>=2){
dp[i] += dp[i-2];
}
else{
dp[i] += 1;
}
}
}
return dp[n-1];
}
}
//前n个字符方式更容易理解，不用单独处理i>=2的方式
public class Solution {
public int NumDecodings(string s) {
int n = s.Length;
int[] dp = new int[n+1]; //dp[i]表示前i个字符的编码方法数
dp[0] = 1; //没有字符是一种编码方法
for(int i=1; i<=n; i++){
if(s[i-1] != '0'){
dp[i] = dp[i-1]; //当前字符不是0，则可以正常编码，使用前面的编码数
}
if(i > 1 && s[i-2] != '0' && Convert.ToInt32(s.Substring(i-2,2)) <= 26 ){
dp[i] += dp[i-2];
}
}
return dp[n];
}
}