解码方法-91

[sl1673495]

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

'A' -> 1
'B' -> 2
...
'Z' -> 26
给定一个只包含数字的非空字符串，请计算解码方法的总数。

示例 1:

输入: "12"
输出: 2
解释: 它可以解码为 "AB"（1 2）或者 "L"（12）。
示例 2:

输入: "226"
输出: 3
解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/decode-ways
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

很坑的一道题，从后往前确定每个字符串下标位置开头会有几种答案，状态转移方程是：

dp[i] = tryOneChar + tryTwoChar

注意：

1. 如果当前位置只选一个字符，如果这个字符是 0，那么不管后面有几种解，这个位置只选一个字符的解都是 0 个。
2. 如果当前位置选两个字符，如果字符的开头是 0 或者字符整体是 00，都视为 0 个解。
3. 注意处理倒数第二个字符时，dp[i + 2] 溢出。

其他没什么了。

/**
 * @param {string} s
 * @return {number}
 */
var numDecodings = function (s) {
    let dp = []
    let n = s.length
    if (!n) {
        return 0
    }

    dp[n - 1] = isZeroStr(s[n - 1]) ? 0 : 1
    for (let i = n - 2; i >= 0; i--) {
        let tryOneChar = 0
        let curChar = s[i]
        if (!isZeroStr(curChar)) {
            tryOneChar = dp[i + 1] === 0 ? 0 : 1 * dp[i + 1]
        }

        let tryTwoChar = 0
        let twoChar = s[i] + s[i + 1]
        if (!isZeroStr(twoChar) && !isZeroStr(curChar) && Number(twoChar) <= 26) {
            tryTwoChar = dp[i + 2] === 0
                ? 0
                : dp[i + 2]
                    ? dp[i + 2] * 1
                    : 1
        }
        dp[i] = tryOneChar + tryTwoChar
    }

    return dp[0]
};

function isZeroStr(str) {
    return Number(str) === 0
}