解码方法

难度:

标签:

题目描述

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

'A' -> "1"
'B' -> "2"
...
'Z' -> "26"

要解码已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"11106" 可以映射为：

"AAJF" ，将消息分组为 (1 1 10 6)
"KJF" ，将消息分组为 (11 10 6)

注意，消息不能分组为 (1 11 06) ，因为 "06" 不能映射为 "F" ，这是由于 "6" 和 "06" 在映射中并不等价。

给你一个只含数字的非空字符串 s ，请计算并返回解码方法的总数。

题目数据保证答案肯定是一个 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 只包含数字，并且可能包含前导零。

代码结果

运行时间: 15 ms, 内存: 16.0 MB

/*
  思路：
  - 使用Java Stream解决这个问题，我们可以定义一个IntStream来表示字符串的长度。
  - 使用reduce操作累积解码方式的数量。
  - 初始值为一个数组，包含两个元素：dp[i-1]和dp[i-2]，代表上一状态的解码数量。
  - 每次迭代更新dp[i-1]和dp[i-2]的值。
*/
 
import java.util.stream.IntStream;
 
public class DecodeWaysStream {
    public int numDecodings(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int n = s.length();
        int[] dp = new int[]{1, s.charAt(0) != '0' ? 1 : 0};
        dp = IntStream.range(2, n + 1).reduce(dp, (prev, i) -> {
            int oneDigit = Integer.parseInt(s.substring(i - 1, i));
            int twoDigits = Integer.parseInt(s.substring(i - 2, i));
            int current = 0;
            if (oneDigit >= 1 && oneDigit <= 9) {
                current += prev[1];
            }
            if (twoDigits >= 10 && twoDigits <= 26) {
                current += prev[0];
            }
            return new int[]{prev[1], current};
        }, (a, b) -> b);
        return dp[1];
    }
}

解释

方法:

这个题解使用动态规划的思想来解决问题。它定义了一个函数f(i)，表示从字符串s的第i个字符开始到末尾的子串有多少种解码方式。然后使用递归的方式，从字符串的最后一个字符开始，逐步计算每个位置的解码方式数量，并将结果存储在dp数组中，避免重复计算。最终返回f(0)，即整个字符串s的解码方式总数。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆

在动态规划解法中，dp数组初始化为-1意味着什么？为什么选择-1作为初始化值？

▷

在动态规划解法中，dp数组初始化为-1表示该位置的解码方式尚未被计算。选择-1作为初始化值是因为解码方式的数量是非负数，使用-1可以明确区分出哪些位置的解码方式已经被计算过（非-1值），哪些还没有被计算（-1值）。这样可以确保每个位置的解码方式只被计算一次，避免不必要的重复计算，提高算法效率。

🦆

递归函数f(i)中，当s[i]为'0'时直接返回0，这是否意味着所有包含'0'的位置都不计入解码方法？

▷

是的，当s[i]为'0'时，按照题目的解码规则，'0'不能单独被解码（没有对应的字母），并且不可以作为两位数的开始（如'01'，'02'等也都不是有效的解码）。因此，如果某位置的字符为'0'，这个位置就不会对解码总数做出贡献。递归函数在遇到'0'时直接返回0，意味着任何以'0'开头的子串都不会有有效的解码方式。

🦆

对于边界条件，动态规划的递归是如何处理字符串s的最后一个字符的？

▷

动态规划的递归处理字符串s的最后一个字符是通过检查是否到达字符串的末尾来实现的。递归函数f(i)中，当i等于字符串长度len(s)时，表示已经处理完所有字符，此时递归到达终止条件，返回1，因为到达字符串末尾是一种有效的结束方式（即之前的所有解码都有效）。

🦆

递归函数中，当s[i]为'2'并且s[i+1]为'7'或更大时，为什么不考虑将s[i]和s[i+1]一起解码？

▷

根据题目的解码规则，只有当数字组合在'10'到'26'之间时，它们才可以被一起解码成一个字母。这是因为这些数字对应于英文字母表的'A'到'Z'。如果s[i]为'2'并且s[i+1]为'7'或更大时（如'27'、'28'等），这些组合超出了'26'的范围，因此不能将它们一起解码为一个字母。所以在这种情况下，这两个字符不能被视为一个有效的两位数解码，递归函数不考虑将它们一起解码。

相关问题

解码方法 II

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

'A' -> "1"
'B' -> "2"
...
'Z' -> "26"

要解码一条已编码的消息，所有的数字都必须分组，然后按原来的编码方案反向映射回字母（可能存在多种方式）。例如，"11106" 可以映射为：

"AAJF" 对应分组 (1 1 10 6)
"KJF" 对应分组 (11 10 6)

注意，像 (1 11 06) 这样的分组是无效的，因为 "06" 不可以映射为 'F' ，因为 "6" 与 "06" 不同。

除了上面描述的数字字母映射方案，编码消息中可能包含 '*' 字符，可以表示从 '1' 到 '9' 的任一数字（不包括 '0'）。例如，编码字符串 "1*" 可以表示 "11"、"12"、"13"、"14"、"15"、"16"、"17"、"18" 或 "19" 中的任意一条消息。对 "1*" 进行解码，相当于解码该字符串可以表示的任何编码消息。

给你一个字符串 s ，由数字和 '*' 字符组成，返回解码该字符串的方法数目。

由于答案数目可能非常大，返回 10⁹ + 7 的模。

示例 1：

输入：s = "*"
输出：9
解释：这一条编码消息可以表示 "1"、"2"、"3"、"4"、"5"、"6"、"7"、"8" 或 "9" 中的任意一条。
可以分别解码成字符串 "A"、"B"、"C"、"D"、"E"、"F"、"G"、"H" 和 "I" 。
因此，"*" 总共有 9 种解码方法。

示例 2：

输入：s = "1*"
输出：18
解释：这一条编码消息可以表示 "11"、"12"、"13"、"14"、"15"、"16"、"17"、"18" 或 "19" 中的任意一条。
每种消息都可以由 2 种方法解码（例如，"11" 可以解码成 "AA" 或 "K"）。
因此，"1*" 共有 9 * 2 = 18 种解码方法。

示例 3：

输入：s = "2*"
输出：15
解释：这一条编码消息可以表示 "21"、"22"、"23"、"24"、"25"、"26"、"27"、"28" 或 "29" 中的任意一条。
"21"、"22"、"23"、"24"、"25" 和 "26" 由 2 种解码方法，但 "27"、"28" 和 "29" 仅有 1 种解码方法。
因此，"2*" 共有 (6 * 2) + (3 * 1) = 12 + 3 = 15 种解码方法。

提示：

1 <= s.length <= 10⁵
s[i] 是 0 - 9 中的一位数字或字符 '*'

子集 II 反转链表 II