解码方法 II

难度:

标签:

题目描述

代码结果

运行时间: 157 ms, 内存: 20.2 MB

/*
 * 解题思路：
 * 1. 使用 Java Stream API 处理字符串，利用 stream 迭代处理字符和子字符串。
 * 2. 通过映射和归约操作计算总解码方法数。
 */
 
import java.util.stream.IntStream;
 
public class DecodeWaysStream {
    private static final int MOD = 1000000007;
 
    public int numDecodings(String s) {
        long[] dp = new long[s.length() + 1];
        dp[0] = 1;
        dp[1] = s.charAt(0) == '*' ? 9 : (s.charAt(0) == '0' ? 0 : 1);
 
        IntStream.range(2, s.length() + 1).forEach(i -> {
            char c1 = s.charAt(i - 1);
            char c2 = s.charAt(i - 2);
 
            if (c1 == '*') {
                dp[i] += 9 * dp[i - 1];
            } else if (c1 != '0') {
                dp[i] += dp[i - 1];
            }
 
            if (c2 == '*') {
                if (c1 == '*') {
                    dp[i] += 15 * dp[i - 2];
                } else if (c1 <= '6') {
                    dp[i] += 2 * dp[i - 2];
                } else {
                    dp[i] += dp[i - 2];
                }
            } else if (c2 == '1' || c2 == '2') {
                if (c1 == '*') {
                    dp[i] += (c2 == '1' ? 9 : 6) * dp[i - 2];
                } else if ((c2 - '0') * 10 + (c1 - '0') <= 26) {
                    dp[i] += dp[i - 2];
                }
            }
 
            dp[i] %= MOD;
        });
 
        return (int) dp[s.length()];
    }
}

解释

方法:

这个题解使用动态规划的思路来解决解码方法的问题。定义 dp[i] 表示字符串的前 i 个字符有多少种解码方法。对于第 i 个字符，需要根据其是数字还是 '*'，以及前一个字符的情况来更新 dp[i]。具体来说： 1. 如果当前字符是 '0'，那么它只能和前一个字符一起解码，并且前一个字符必须是 '1' 或 '2'，否则无法解码。 2. 如果当前字符是 '1'~'6'，那么它可以单独解码，也可以和前一个字符一起解码（如果前一个字符是 '1' 或 '2'）。 3. 如果当前字符是 '7'~'9'，那么它只能单独解码，或者和前一个字符一起解码（如果前一个字符是 '1'）。 4. 如果当前字符是 '*'，那么它可以表示 '1'~'9' 中的任意数字，需要根据前一个字符是 '1'、'2' 还是其他数字来更新 dp[i]。最终的答案即为 dp[n-1]，也就是整个字符串的解码方法数目。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆

在动态规划解法中，为什么要对结果取模10^9+7？这个数字有什么特殊的意义吗？

▷

在计算机科学中，经常使用模运算来防止数值溢出，尤其是在涉及大数运算的情况。10^9+7 是一个常用的大质数，使用它作为模数有几个好处：1) 它足够大，可以保证大多数计算不会产生溢出；2) 它是质数，这有助于在某些数学运算中保持良好的分布性；3) 它适合用于模算术，因为具有良好的性能和分布特性。使用此模数帮助我们在不丢失数据精度的前提下，处理大规模数据。

🦆

题解中提到如果当前字符是'0'，只能和前一个字符一起解码。如果前一个字符也是'*'，该如何处理？

▷

当当前字符是'0'而前一个字符是'*'时，'*'可以代表'1'或'2'（因为只有'10'和'20'是有效的编码）。因此，如果 s[i-1] 是 '*'，则 '*' 可以解码为 '1' 或 '2'，使得组合为 '10' 或 '20'。因此，dp[i] 应该等于 dp[i-2] 的值（如果 i>1），如果 i=1，则 dp[i] 应该为 2（即有两种情况：'10' 和 '20'）。

🦆

为什么当当前字符为'*'且前一个字符为'1'或'2'时，有不同的解码方式数量计算？具体是如何计算这些解码方式的？

▷

当当前字符为'*'时，它可以代表从'1'到'9'的任意数字。如果前一个字符是'1'，那么 '*' 可以形成与 '1' 的组合，即 '11' 到 '19'，共9种情况。如果前一个字符是'2'，'*' 可以形成 '21' 到 '26'，共6种情况（因为只有'21'到'26'是有效的编码）。因此，当 s[i-1] 是 '1' 或 '2' 时，dp[i] 的更新规则应分别添加 dp[i-2]*9（如果前一个字符是 '1'）和 dp[i-2]*6（如果前一个字符是 '2'），来反映这些额外的组合解码方式。

🦆

题解中提到，如果当前字符是'1'~'6'，可以单独解码或和前一个字符一起解码。如果前一个字符是'*'，为何解码方式数是当前dp[i-1]加上dp[i-2]的两倍？

▷

当当前字符在'1'~'6'范围内时，可以单独解码。如果前一个字符是'*'，则 '*' 可以代表 '1' 或 '2'。这意味着，除了可以单独解码当前字符外，还可以与前一个字符形成有效的双字符编码（例如，'*1'， '*2'，'*3'，'*4'，'*5'，'*6'，其中'*'可以是'1'或'2'）。因此，对于每个这样的双字符组合，都有一种额外的解码方式，即 dp[i-2]。因此，dp[i] 更新为 dp[i-1] 加上 dp[i-2] 的两倍，反映了这两种可能性（'*'代表'1'和'*'代表'2'）。

解码方法 II

题目描述

代码结果

解释

代码细节讲解

相关问题

解码方法