我们先来描述这个问题：
例如：您截获了一条编码为数字字符串的秘密消息。该消息通过以下映射解码：
“1”-> 'A'“2”-> 'B' ...“25”-> 'Y'“26”-> 'Z'
但是，在解码消息时，您意识到可以通过多种不同的方式解码消息，因为某些代码包含在其他代码中（“2”和“5”与“25”）。
例如“11106”可以解码为：
- “AAJF”，分组为 (1, 1, 10, 6)
- “KJF”与分组 (11, 10, 6)
- 分组（1, 11, 06）无效，因为“06”不是有效代码（只有“6”有效）。
注意：可能存在无法解码的字符串。
给定一个仅包含数字的字符串 s，返回解码它的方法数。如果整个字符串无法以任何有效方式解码，则返回 0。
生成测试用例，以便答案适合32位整数。
Input: s = "12" Output: 2 Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).
Input: s = "226" Output: 3 Explanation: "226" could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
Input: s = "06"
Output: 0
Explanation: "06" cannot be mapped to "F" because of the leading zero ("6" is different from "06"). In this case, the string is not a valid encoding, so return 0.
首先，让我们从最简单的见解开始：一个字符可以被解码为它本身（仅一个字符）或两位数字的一部分。
如果是第一个选项，我们只能使用 1 到 9 之间的数字，因为 0 本身不映射到任何东西。
但是，两位数的范围可以是 10 到 26。
与爬楼梯非常相似，我们必须使用长度 s.length + 1 初始化数组，因为我们需要考虑我们尚未解码任何内容的事实。
换句话说，当没有字符时，只有
一种方式来“解码”：根本不解码。
let dp = Array.from({ length: s.length + 1 }, () => 0);
dp[0] = 1;
我们知道，如果它是“0”，我们就无法对其进行解码，因此在这种情况下解码它的方法数将为 0。
请注意，
无法解码与根本不进行任何解码不同：在第一种情况下，解码方式的数量为0，但在第二种情况下（如我们刚刚用 dp[0] 做了），可以说解码的方式数量是 1。
一种方法来解码它，因为它只是一个字符。因此，我们将相应地初始化 dp[1]：
dp[1] = (s[0] === '0') ? 0 : 1;
只要前一个数字不是数字 0，我们就可以添加数组前一个槽中的任何内容。
而且，只要前两位数字构成10到26之间的数字，我们也可以添加相应的解决方案。总而言之，它可以看起来像这样：
for (let i = 2; i <= s.length; i++) {
const prevDigit = s[i - 1];
const twoPrevDigits = s.slice(i - 2, i);
if (+prevDigit !== 0) {
dp[i] += dp[i - 1];
}
if (10 <= +twoPrevDigits && +twoPrevDigits <= 26) {
dp[i] += dp[i - 2];
}
}
At this point, we have the result in the last index (which corresponds to s.length) so we can just return it:
function numDecodings(s: string): number {
/* ... */
return dp[s.length];
}
Overall, this is how our solution looks like:
function numDecodings(s: string): number {
let dp = Array.from({ length: s.length + 1 }, () => 0);
dp[0] = 1;
dp[1] = (s[0] === '0') ? 0 : 1;
for (let i = 2; i <= s.length; i++) {
const prevDigit = s[i - 1];
const twoPrevDigits = s.slice(i - 2, i);
if (+prevDigit !== 0) {
dp[i] += dp[i - 1];
}
if (10 <= +twoPrevDigits && +twoPrevDigits <= 26) {
dp[i] += dp[i - 2];
}
}
return dp[s.length];
}
Both the time and space complexity for this solution are O(n) as we iterate through all the characters doing a constant operation, and we have to keep an array whose size will grow as our input size increases.
Next up is the problem called Coin Change. Until then, happy coding.
以上是LeetCode 冥想：解码方法的详细内容。更多信息请关注PHP中文网其他相关文章！
