91. Decode Ways

Leetcode link

题目简介

/**
 * @param {string} s
 * @return {number}
 */

题目给我们一个数字字符串 s，s 是通过一些规则进行编码的字符串，规则如下：

"1" -> 'A'
"2" -> 'B'
...
"25" -> 'Y'
"26" -> 'Z'

但是这个规则下，字符串的解码有多种可能，比如：

"11106"

(1, 1, 10, 6) -> "AAJF"
(11, 10, 6) -> "KJF"

题目要我们求出给定字符串 s，会有多少种解法

解题思路

我们可以从最简单的长度为 3 的字符串开始思考："126"

• 1：只有一个选择
• 2：有两个选择（2 或者 12）
• 6：
  • 如果选择 6 自己，就跟上述 2 的选择一样（2 个选择）
  • 如果选择 26，则跟上述 1 的选择一样（1 个选择）

至此，我们可以得到状态转移方程：

dp[i] = dp[i-1] + dp[i-2]

这个转移方程还缺失了两块：

• 如果可以用 dp[i-1] 我们需要 s[i] 范围是 [1, 9]（不能为 0）
• 如果可以用 dp[i-2] 我们需要 s[i-1]s[i] 组成数字的范围是 [10, 26]

为了计算方便，我们可以让 dp 数组长度为 s.length+1

最后我们返回 dp[s.length] 即可

Javascript

/**
 * @param {string} s
 * @return {number}
 */
var numDecodings = function (s) {
    if (s[0] === '0') {
        return 0
    }
    const len = s.length
    const dp = Array(len + 1).fill(0)
    dp[0] = 1
    dp[1] = 1
    for (let i = 2; i <= s.length; i++) {
        const one = parseInt(s[i - 1], 10)
        const two = parseInt(`${s[i - 2]}${s[i - 1]}`, 10)
        if (one > 0) {
            dp[i] += dp[i - 1]
        }
        if (two <= 26 && two > 9) {
            dp[i] += dp[i - 2]
        }
    }
    return dp[len]
};

复杂度分析

时间

O(n)

空间

O(n)