91. 解码方法
题目描述
一条包含字母 A-Z
的消息通过以下映射进行了 编码 :
"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 位 的整数。
示例 1:
输入:s = "12" 输出:2 解释:它可以解码为 "AB"(1 2)或者 "L"(12)。
示例 2:
输入:s = "226" 输出:3 解释:它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
示例 3:
输入:s = "06" 输出:0 解释:"06" 无法映射到 "F" ,因为存在前导零("6" 和 "06" 并不等价)。
提示:
1 <= s.length <= 100
s
只包含数字,并且可能包含前导零。
解法
方法一:动态规划
我们定义 \(f[i]\) 表示字符串的前 \(i\) 个字符的解码方法数,初始时 \(f[0]=1\),其余 \(f[i]=0\)。
考虑 \(f[i]\) 如何进行状态转移。
- 如果第 \(i\) 个字符(即 \(s[i-1]\))单独形成编码,那么它对应一种解码方式,即 \(f[i]=f[i-1]\)。前提是 \(s[i-1] \neq 0\)。
- 如果第 \(i-1\) 个字符和第 \(i\) 个字符组成的字符串在 \([1,26]\) 范围内,那么它们可以作为一个整体,对应一种解码方式,即 \(f[i] = f[i] + f[i-2]\)。前提是 \(s[i-2] \neq 0\),且 \(s[i-2]s[i-1]\) 在 \([1,26]\) 范围内。
时间复杂度 \(O(n)\),空间复杂度 \(O(n)\)。其中 \(n\) 是字符串的长度。
1 2 3 4 5 6 7 8 9 10 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
我们注意到,状态 \(f[i]\) 仅与状态 \(f[i-1]\) 和状态 \(f[i-2]\) 有关,而与其他状态无关,因此我们可以使用两个变量代替这两个状态,使得原来的空间复杂度 \(O(n)\) 降低至 \(O(1)\)。
1 2 3 4 5 6 7 8 9 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|