Skip to content

Latest commit

 

History

History
177 lines (128 loc) · 4.03 KB

91.decode-ways.md

File metadata and controls

177 lines (128 loc) · 4.03 KB

题目地址(91. 解码方法)

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

题目描述

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

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

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

 

示例 1:

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

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

输入:s = "0"
输出:0
示例 4:

输入:s = "1"
输出:1
示例 5:

输入:s = "2"
输出:1
 

提示:

1 <= s.length <= 100
s 只包含数字,并且可以包含前导零。

前置知识

公司

  • 阿里
  • 腾讯
  • 百度
  • 字节

思路

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

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

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

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

关于递归公式,让我们先局部后整体

对于局部,我们遍历到一个元素的时候,有两种方式来组成编码方式,第一种是这个元素本身(需要自身是[1,9]),第二种是它和前一个元素组成[10, 26]。

用伪代码来表示的话就是:dp[i] = 以自身去编码(一位) + 以前面的元素和自身去编码(两位) ,这显然是完备的,这样我们就通过层层推导得到结果。

关键点解析

  • 爬楼梯问题(我把这种题目统称为爬楼梯问题)

代码

代码支持: JS, Python3,CPP

JS Code:

/**
 * @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];
};

Python3 Code:

class Solution:
    def numDecodings(self, s: str) -> int:
        @lru_cache(None)
        def dp(start):
            if start == len(s):
                return 1
            if start > len(s):
                return 0
            if s[start] != "0":
                if s[start : start + 2] <= "26":
                    return dp(start + 1) + dp(start + 2)
                return dp(start + 1)
            return 0

        return dp(0)

复杂度分析

  • 时间复杂度:$O(N)$
  • 空间复杂度:$O(N)$

实际上,我们也可以使用滚动数组优化。

CPP code:

class Solution {
public:
  int numDecodings(string s) {
    int pre2 = 0, pre1 = 1;
    for (int i = 0; i < s.size() && pre1; ++i) {
      int cur = 0;
      if (s[i] != '0') cur += pre1;
      if (i != 0 && s[i - 1] != '0' && (s[i - 1] - '0') * 10 + s[i] - '0' <= 26)
        cur += pre2;
      pre2 = pre1;
      pre1 = cur;
    }
    return pre1;
  }
};

复杂度分析

  • 时间复杂度:$O(N)$
  • 空间复杂度:$O(1)$

扩展

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

大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。