91.decode-ways.md

题目地址

https://leetcode.com/problems/decode-ways/description/

题目描述

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26
Given a non-empty string containing only digits, determine the total number of ways to decode it.

Example 1:

Input: "12"
Output: 2
Explanation: It could be decoded as "AB" (1 2) or "L" (12).
Example 2:

Input: "226"
Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

思路

这道题目和爬楼梯问题有异曲同工之妙。

这也是一道典型的动态规划题目。我们来思考：

• 对于一个数字来说[1,9]这九个数字能够被识别为一种编码方式
• 对于两个数字来说[10, 26]这几个数字能被识别为一种编码方式

我们考虑用dp[i]来切分子问题， 那么dp[i]表示的意思是当前字符串的以索引i结尾的子问题。 这样的话，我们最后只需要取dp[s.length] 就可以解决问题了。

关于递归公式，让我们先局部后整体。对于局部，我们遍历到一个元素的时候， 我们有两种方式来组成编码方式，第一种是这个元素本身（需要自身是[1,9]）, 第二种是它和前一个元素组成[10, 26]。 用伪代码来表示的话就是： dp[i] = 以自身去编码（一位） + 以前面的元素和自身去编码（两位） .这显然是完备的， 这样我们通过层层推导就可以得到结果。

关键点解析

• 爬楼梯问题（我把这种题目统称为爬楼梯问题）

代码

/*
 * @lc app=leetcode id=91 lang=javascript
 *
 * [91] Decode Ways
 *
 * https://leetcode.com/problems/decode-ways/description/
 *
 * algorithms
 * Medium (21.93%)
 * Total Accepted:    254.4K
 * Total Submissions: 1.1M
 * Testcase Example:  '"12"'
 *
 * A message containing letters from A-Z is being encoded to numbers using the
 * following mapping:
 *
 *
 * 'A' -> 1
 * 'B' -> 2
 * ...
 * 'Z' -> 26
 *
 *
 * Given a non-empty string containing only digits, determine the total number
 * of ways to decode it.
 *
 * Example 1:
 *
 *
 * Input: "12"
 * Output: 2
 * Explanation: It could be decoded as "AB" (1 2) or "L" (12).
 *
 *
 * Example 2:
 *
 *
 * Input: "226"
 * Output: 3
 * Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2
 * 6).
 *
 */
/**
 * @param {string} s
 * @return {number}
 */
var numDecodings = function(s) {
  if (s == null || s.length == 0) {
    return 0;
  }
  const dp = Array(s.length + 1).fill(0);
  dp[0] = 1;
  dp[1] = s[0] !== "0" ? 1 : 0;
  for (let i = 2; i < s.length + 1; i++) {
     const one = +s.slice(i - 1, i);
     const two = +s.slice(i - 2, i);

    if (two >= 10 && two <= 26) {
      dp[i] = dp[i - 2];
    }

    if (one >= 1 && one <= 9) {
      dp[i] += dp[i - 1];
    }
  }

  return dp[dp.length - 1];
};

扩展

如果编码的范围不再是1-26，而是三位的话怎么办？