我们先来描述这个问题:
您截获了一条编码为数字字符串的秘密消息。该消息通过以下映射进行解码:
“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。
与本章前面的问题一样,我们可以首先创建一个 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时间和空间复杂度
该解决方案的时间和空间复杂度均为 在) 当我们迭代所有字符进行常量操作时,我们必须保留一个数组,其大小将随着输入大小的增加而增加。
接下来是硬币找零的问题。在那之前,祝您编码愉快。
免责声明: 提供的所有资源部分来自互联网,如果有侵犯您的版权或其他权益,请说明详细缘由并提供版权或权益证明然后发到邮箱:[email protected] 我们会第一时间内为您处理。
Copyright© 2022 湘ICP备2022001581号-3