加载中...

daily leetcode - decode-ways - !

题目地址

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

题目描述

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).

思路

这道题要求解码方法,跟之前那道 Climbing Stairs 非常的相似,但是还有一些其他的限制条件,比如说一位数时不能为 0,两位数不能大于 26,其十位上的数也不能为 0,除去这些限制条件,跟爬梯子基本没啥区别,也勉强算特殊的斐波那契数列,当然需要用动态规划 Dynamci Programming 来解。建立一维 dp 数组,其中 dp[i] 表示 s 中前 i 个字符组成的子串的解码方法的个数,长度比输入数组长多多 1,并将 dp[0] 初始化为 1。现在来找状态转移方程,dp[i] 的值跟之前的状态有着千丝万缕的联系,就拿题目中的例子 2 来分析吧,当 i=1 时,对应 s 中的字符是 s[0]='2',只有一种拆分方法,就是 2,注意 s[0] 一定不能为 0,这样的话无法拆分。当 i=2 时,对应 s 中的字符是 s[1]='2',由于 s[1] 不为 0,那么其可以被单独拆分出来,就可以在之前 dp[i-1] 的每种情况下都加上一个单独的 2,这样 dp[i] 至少可以有跟 dp[i-1] 一样多的拆分情况,接下来还要看其能否跟前一个数字拼起来,若拼起来的两位数小于等于 26,并且大于等于 10(因为两位数的高位不能是 0),那么就可以在之前 dp[i-2] 的每种情况下都加上这个二位数,所以最终 dp[i] = dp[i-1] + dp[i-2],是不是发现跟斐波那契数列的性质吻合了。所以 0 是个很特殊的存在,若当前位置是 0,则一定无法单独拆分出来,即不能加上 dp[i-1],就只能看否跟前一个数字组成大于等于 10 且小于等于 26 的数,能的话可以加上 dp[i-2],否则就只能保持为 0 了。具体的操作步骤是,在遍历的过程中,对每个数字首先判断其是否为 0,若是则将 dp[i] 赋为 0,若不是,赋上 dp[i-1] 的值,然后看数组前一位是否存在,如果存在且满足前一位是 1,或者和当前位一起组成的两位数不大于 26,则当前 dp[i] 值加上 dp[i - 2]。最终返回 dp 数组的最后一个值即可,代码如下:

C++ 解法一:

class Solution {
public:
    int numDecodings(string s) {
        if (s.empty() || s[0] == '0') return 0;
        vector<int> dp(s.size() + 1, 0);
        dp[0] = 1;
        for (int i = 1; i < dp.size(); ++i) {
            dp[i] = (s[i - 1] == '0') ? 0 : dp[i - 1];
            if (i > 1 && (s[i - 2] == '1' || (s[i - 2] == '2' && s[i - 1] <= '6'))) {
                dp[i] += dp[i - 2];
            }
        }
        return dp.back();
    }
};

Java 解法一:

class Solution {
    public int numDecodings(String s) {
        if (s.isEmpty() || s.charAt(0) == '0') return 0;
        int[] dp = new int[s.length() + 1];
        dp[0] = 1;
        for (int i = 1; i < dp.length; ++i) {
            dp[i] = (s.charAt(i - 1) == '0') ? 0 : dp[i - 1];
            if (i > 1 && (s.charAt(i - 2) == '1' || (s.charAt(i - 2) == '2' && s.charAt(i - 1) <= '6'))) {
                dp[i] += dp[i - 2];
            }
        }
        return dp[s.length()];
    }
}

下面这种方法跟上面的方法的思路一样,只是写法略有不同:

C++ 解法二:

class Solution {
public:
    int numDecodings(string s) {
        if (s.empty() || s[0] == '0') return 0;
        vector<int> dp(s.size() + 1, 0);
        dp[0] = 1;
        for (int i = 1; i < dp.size(); ++i) {
            if (s[i - 1] != '0') dp[i] += dp[i - 1];
            if (i >= 2 && s.substr(i - 2, 2) <= "26" && s.substr(i - 2, 2) >= "10") {
                dp[i] += dp[i - 2];
            }
        }
        return dp.back();
    }
};

Java 解法二:

class Solution {
    public int numDecodings(String s) {
        if (s.isEmpty() || s.charAt(0) == '0') return 0;
        int[] dp = new int[s.length() + 1];
        dp[0] = 1;
        for (int i = 1; i < dp.length; ++i) {
            if (s.charAt(i - 1) != '0') dp[i] += dp[i - 1];
            if (i >= 2 && (s.substring(i - 2, i).compareTo("10") >= 0 && s.substring(i - 2, i).compareTo("26") <= 0)) {
                dp[i] += dp[i - 2];
            }
        }
        return dp[s.length()];
    }
}

我们再来看一种空间复杂度为 O(1) 的解法,用两个变量 a, b 来分别表示 s[i-1] 和 s[i-2] 的解码方法,然后从 i=1 开始遍历,也就是字符串的第二个字符,判断如果当前字符为 '0',说明当前字符不能单独拆分出来,只能和前一个字符一起,先将 a 赋为 0,然后看前面的字符,如果前面的字符是 1 或者 2 时,就可以更新 a = a + b,然后 b = a - b,其实 b 赋值为之前的 a,如果不满足这些条件的话,那么 b = a,参见代码如下:

C++ 解法三:

class Solution {
public:
    int numDecodings(string s) {
        if (s.empty() || s[0] == '0') return 0;
        int a = 1, b = 1, n = s.size();
        for (int i = 1; i < n; ++i) {
            if (s[i] == '0') a = 0;
            if (s[i - 1] == '1' || (s[i - 1] == '2' && s[i] <= '6')) {
                a = a + b;
                b = a - b;
            } else {
                b = a;
            }
        }
        return a;
    }
};

Java 解法三:

class Solution {
    public int numDecodings(String s) {
        if (s.isEmpty() || s.charAt(0) == '0') return 0;
        int a = 1, b = 1, n = s.length();
        for (int i = 1; i < n; ++i) {
            if (s.charAt(i) == '0') a = 0;
            if (s.charAt(i - 1) == '1' || (s.charAt(i - 1) == '2' && s.charAt(i) <= '6')) {
                a = a + b;
                b = a - b;
            } else {
                b = a;
            }
        }
        return a;
    }
}

思路 2

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

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

  • 对于一个数字来说[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,而是三位的话怎么办?

本文参考自:
https://github.com/grandyang/leetcode/ &
https://github.com/azl397985856/leetcode


标题: daily leetcode - decode-ways - !
文章作者: lonuslan
文章链接: https://www.lonuslan.com/articles/2020/03/15/1584241333790.html
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Hi I'm LonusLan 👋🏼

评论