LeetCode 冥想：解码方法

发布于2024-08-01

LeetCode Meditations: Decode Ways

我们先来描述这个问题：

您截获了一条编码为数字字符串的秘密消息。该消息通过以下映射进行解码：

“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
s 仅包含数字，并且可能包含前导零。

我认为这是您乍一看并不那么困难的问题之一，直到您尝试解决它为止。

首先，让我们从最简单的见解开始：一个字符可以被解码为它本身（仅一个字符）或两位数的一部分。
如果它是第一个选项，我们只能有从 1 到 9 的数字，因为 0 本身不映射到任何东西。
但是，两位数的范围可以是 10 到 26。

与本章前面的问题一样，我们可以首先创建一个 dp 数组来保存迭代字符串时每个字符的解码方式数量。
与爬楼梯非常相似，我们必须使用长度 s.length 1 初始化数组，因为我们需要考虑我们尚未解码任何内容的事实。
换句话说，当没有字符时，只有一种方式来“解码”：根本不解码。

因此，我们可以将所有值初始化为 0，除了第一个索引将是 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 只包含数字。




此时，我们在最后一个索引（对应于 s.length）中得到了结果，因此我们可以返回它：



function numDecodings(s: string): number {
  /* ... */

  return dp[s.length]; 
}




总的来说，我们的解决方案是这样的：



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 




  
  
  时间和空间复杂度


该解决方案的时间和空间复杂度均为


   $O (n) O(n)$ 
 当我们迭代所有字符进行常量操作时，我们必须保留一个数组，其大小将随着输入大小的增加而增加。




接下来是硬币找零的问题。在那之前，祝您编码愉快。