LeetCode 冥想：解码方法

我们先来描述这个问题：

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

“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.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];
}

Time and space complexity

Both the time and space complexity for this solution are $O(n)$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中文网其他相关文章！