以下是一道解密数字字符串的算法题,需要将数字转化为相应字符。请提供完整的问题描述和参考代码。我查阅了一些解决方案,发现所有的解码方法都是从后往前解码,但我认为也可以从前往后解码,请问从后往前解码有什么特殊的优势或者考虑因素吗?谢谢。
给定一个由字母 A-Z 组成的消息,使用下列映射将其编码为数字:
'A' -> 1 'B' -> 2 ... 'Z' -> 26
给定一个包含数字的编码消息,确定总共有多少种解码方式。
例如,给定编码消息 "12",它可以解码为 "AB" (1 2) 或者 "L" (12)。
解码 "12" 的方法有 2 种。
给定一个由字母 A-Z 组成的消息,使用下列映射将其编码为数字:
'A' -> 1 'B' -> 2 ... 'Z' -> 26
给定一个包含数字的编码消息,确定总共有多少种解码方式。
例如,给定编码消息 "12",它可以解码为 "AB" (1 2) 或者 "L" (12)。
解码 "12" 的方法有 2 种。
public class Solution {
public int numDecodings(String s) {
int n = s.length();
if (n == 0) return 0;
int[] memo = new int[n+1];
memo[n] = 1;
memo[n-1] = s.charAt(n-1) != '0' ? 1 : 0;
for (int i = n - 2; i >= 0; i--)
if (s.charAt(i) == '0') continue;
else memo[i] = (Integer.parseInt(s.substring(i,i+2))<=26) ? memo[i+1]+memo[i+2] : memo[i+1];
return memo[0];
}
}
thanks in advance, Lin
int(st[i-1]) == 0
的情况下,语句result_dict[st[:i]] = 0
和result_dict[st[:i]] = result_dict[st[:i-1]]
都会被执行,后者会覆盖前者吗?谢谢。 - Lin Ma列表索引
中。因此,对于2101
的结果列表是[1,2,1,1]
,这意味着2-1种方式
,21-2种方式(2,1和21)
,210-1种方式(2,10)
,2101-1种方式(2,10,1)
。所以对于'2101',当字符为'0'时,您必须已经得到了'1'。我希望现在你的疑惑已经解决了 :) - Termi