Open
Description
一条包含字母 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注意：
- 如果当前位置只选一个字符，如果这个字符是
0，那么不管后面有几种解，这个位置只选一个字符的解都是 0 个。 - 如果当前位置选两个字符，如果字符的开头是
0或者字符整体是00，都视为 0 个解。 - 注意处理倒数第二个字符时，
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
}