[LeetCode] 91. Decode Ways

You have intercepted a secret message encoded as a string of numbers. The message is decoded via the following mapping:

“1” -> ‘A’
“2” -> ‘B’
…

“25” -> ‘Y’
“26” -> ‘Z’

However, while decoding the message, you realize that there are many different ways you can decode the message because some codes are contained in other codes (“2” and “5” vs “25”).

For example, “11106” can be decoded into:
“AAJF” with the grouping (1, 1, 10, 6)
“KJF” with the grouping (11, 10, 6)
The grouping (1, 11, 06) is invalid because “06” is not a valid code (only “6” is valid).
Note: there may be strings that are impossible to decode.

Given a string s containing only digits, return the number of ways to decode it. If the entire string cannot be decoded in any valid way, return 0.

The test cases are generated so that the answer fits in a 32-bit integer.

Example 1:
Input: s = “12”
Output: 2

Explanation:
“12” could be decoded as “AB” (1 2) or “L” (12).

Example 2:
Input: s = “226”
Output: 3

Explanation:
“226” could be decoded as “BZ” (2 26), “VF” (22 6), or “BBF” (2 2 6).

Example 3:
Input: s = “06”
Output: 0

Explanation:
“06” cannot be mapped to “F” because of the leading zero (“6” is different from “06”). In this case, the string is not a valid encoding, so return 0.

Constraints:
1 <= s.length <= 100
s contains only digits and may contain leading zero(s).

解码方法。

一条包含字母 A-Z 的消息通过以下映射进行了 编码 ： "1" -> 'A'

“2” -> ‘B’

…

“25” -> ‘Y’

“26” -> ‘Z’

然而，在 解码 已编码的消息时，你意识到有许多不同的方式来解码，因为有些编码被包含在其它编码当中（”2” 和 “5” 与 “25”）。

例如，”11106” 可以映射为：
“AAJF” ，将消息分组为 (1, 1, 10, 6)
“KJF” ，将消息分组为 (11, 10, 6)
消息不能分组为 (1, 11, 06) ，因为 “06” 不是一个合法编码（只有 “6” 是合法的）。
注意，可能存在无法解码的字符串。

给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。如果没有合法的方式解码整个字符串，返回 0。

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

思路

思路是动态规划，这是一道类似爬楼梯那一类的题目。这个题 dp[i] 的定义是前 i 个数字能产生的解码方法的总数。因为解码是从数字到字母，所以有效的数字就只能在 1 到 26 之间，所以

• 如果 input 有 leading zero 的话，直接返回 0，无法解码
• 中间过程中，在遍历到位置 i 的时候，需要看(i - 1, i)和(i - 2, i)是否能组成一个有效的数字
• 如果 (i - 1, i) 在 1 - 9 之间，则说明当前位置上的数字可以组成一个有效的一位数
• 如果 (i - 2, i) 在 10 - 26 之间，则说明当前位置上的数字可以和前面一个数字组成一个有效的两位数

复杂度

时间O(n)
空间O(n)

代码

Java实现

class Solution {
    public int numDecodings(String s) {
        // corner case
        if (s == null || s.length() == 0 || s.charAt(0) == '0') {
            return 0;
        }

        // normal case
        int n = s.length();
        int[] dp = new int[n + 1];
        dp[0] = 1; // 空字符串
        dp[1] = 1; // 第一个字符不是0时有1种解码方式
        for (int i = 2; i <= n; i++) {
            char one = s.charAt(i - 1);
            char two = s.charAt(i - 2);

            // 如果当前这一位是0，他不能单独解码
            // 只有和前一位组成10或20时才能解码
            // [1, 2, 0]
            if (one >= '1' && one <= '9') {
                dp[i] += dp[i - 1];
            }

            // 两位字符解码（10~26）
            int num = (two - '0') * 10 + (one - '0');
            if (num >= 10 && num <= 26) {
                dp[i] += dp[i - 2];
            }
        }
        return dp[n];
    }
}

JavaScript实现

/**
 * @param {string} s
 * @return {number}
 */
var numDecodings = function (s) {
	// corner case
	if (s == null || s.length == 0) {
		return 0;
	}

	// normal case
	let n = s.length;
	let dp = new Array(n + 1).fill(0);
	dp[0] = 1;
	dp[1] = s.charAt(0) != '0' ? 1 : 0;
	for (let i = 2; i <= n; i++) {
		let first = s.substring(i - 1, i);
		let second = s.substring(i - 2, i);
		if (first >= 1 && first <= 9) {
			dp[i] += dp[i - 1];
		}
		if (second >= 10 && second <= 26) {
			dp[i] += dp[i - 2];
		}
	}
	return dp[n];
};