91. 解码方法

🟠   🔖  字符串 动态规划  🔗 力扣 LeetCode

题目

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 位 的整数。

示例 1：

输入： s = "12"

输出： 2

解释： 它可以解码为 "AB"（1 2）或者 "L"（12）。

示例 2：

输入： s = "226"

输出： 3

解释： 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。

示例 3：

输入： s = "06"

输出： 0

解释： "06" 无法映射到 "F" ，因为存在前导零（"6" 和 "06" 并不等价）。

提示：

• 1 <= s.length <= 100
• s 只包含数字，并且可能包含前导零。

解题思路

可以用 动态规划 来解决这道题。

1. 状态定义：

   • 用 dp[i] 表示解码前 i 个字符的方法总数。

2. 状态转移方程：

   • 如果当前字符 s[i-1] 可以单独解码（1 <= s[i-1] <= 9），则 dp[i] += dp[i-1]。
   • 如果当前字符与前一个字符组合可以解码（10 <= s[i-2..i-1] <= 26），则 dp[i] += dp[i-2]。

3. 初始化：

   • dp[0] = 1：空字符串有一种解码方式。
   • dp[1] = 1：第一个字符非零时只有一种解码方式。

4. 特殊情况：

   • 如果字符串以 0 开头，则无法解码，直接返回 0。

5. 最终结果：

   • 返回 dp[n]，即解码整个字符串的方法数。

复杂度分析

• 时间复杂度：O(n)，遍历字符串一次。
• 空间复杂度：O(n)，使用了大小为 n+1 的数组 dp，可以优化为只使用两个变量 prev2 和 prev1 来表示 dp[i-2] 和 dp[i-1]，从而将空间复杂度降为 O(1)。

代码

/**
 * @param {string} s
 * @return {number}
 */
var numDecodings = function (s) {
	if (s[0] === '0') return 0; // 字符串以0开头无法解码

	const n = s.length;
	let dp = new Array(n + 1).fill(0);
	dp[0] = 1; // 空字符串初始化
	dp[1] = 1; // 第一个字符有效时初始化为1

	for (let i = 2; i <= n; i++) {
		const one = Number(s[i - 1]); // 单独解码当前字符
		const two = Number(s.slice(i - 2, i)); // 解码当前和前一个字符组合

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

	return dp[n];
};

相关题目

题号	标题	题解	标签	难度	力扣
639	解码方法 II		字符串 动态规划	🔴	🀄️ 🔗
1977	划分数字的方案数		字符串 动态规划 后缀数组	🔴	🀄️ 🔗
2266	统计打字方案数		哈希表 数学 字符串 1+	🟠	🀄️ 🔗