Ricky.L的随笔
0%

LeetCode.91.解码方法（中等）

发表于 更新于 分类于 Disqus：

题目

LeetCode.91.解码方法（中等）

一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：

‘A’ -> 1
‘B’ -> 2
…
‘Z’ -> 26

要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，”11106” 可以映射为：

  • “AAJF” ，将消息分组为 (1 1 10 6)
  • “KJF” ，将消息分组为 (11 10 6)

注意，消息不能分组为 (1 11 06) ，因为 “06” 不能映射为 “F” ，这是由于 “6” 和 “06” 在映射中并不等价。

给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。

题目数据保证答案肯定是一个 32 位 的整数。

题解

思考能否将某个状态下的问题拆分为子问题+有限步骤。

设a[i]为s[0..i]中解码方法总数。

a[i]取值受什么影响？

受s[i - 1]和s[i - 2]的取值影响，因为要决定是解析一个字符还是两个字符。
a[i]可以通过a[i - 1]或a[i - 2]递推而来。

s[i - 1]和s[i - 2]组合的数有哪些情况？

根据题意，没有直接映射到0的情况，要注意：

  1. 不能单独映射0，只能作为10或者20整体解析，方案数不变，a[i] = a[i - 1]。一旦出现0的前面不是1或2，整个s无法解析，直接返回0方案数。
  2. 06这样的0处在十位数的也不能作为个位数解析，只能一个个解析，方案数不变，a[i] = a[i - 1]

两个数字剩余的合法取值范围在[11, 19]、[21, 26]，此时可以映射一个字母，也可以映射两个字母。
a[i] = a[i - 1] + a[i - 2]

其他大于26的情况，只能映射一个字母，方案数不变，a[i] = a[i - 1]

空间优化

a[i]只与前两个状态有关，只用两个保存状态即可，不需要数组记录所有状态。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
    fun numDecodings(s: String): Int {
        val n = s.length
        if (n == 0) return 0
        if (s[0] == '0') return 0
        if (n == 1) return 1

        // 初始的一个字符只有一种映射方案
        var prepre = 1

        // 初始时，前两个字符的解析方案数
        var pre = if (s[1] == '0') {
            if (s[0] == '1' || s[0] == '2') prepre
            else return 0
        } else {
            val num = parseInt(s[0], s[1])
            if (num in 11..19 || num in 21..26) 2 else 1
        }

        var cur = pre
        
        // 从第3个字符开始解析
        for (i in 2 until n) {
            cur = if (s[i] == '0') {
                if (s[i - 1] == '1' || s[i - 1] == '2') prepre
                else return 0
            } else {
                val num = parseInt(s[i - 1], s[i])
                if (num in 11..19 || num in 21..26) pre + prepre else pre
            }
            prepre = pre
            pre = cur
        }

        return cur
    }

    private fun parseInt(a: Char, b: Char): Int {
        val tens = (a.toInt() - '0'.toInt()) * 10
        val units = b.toInt() - '0'.toInt()
        return tens + units
    }
}