当前位置：首页 > news >正文

题解：学而思编程单词解密

news 2026/6/14 11:06:54

【题目来源】

学而思编程：单词解密

【题目描述】

小猴发明了一套对字母的加密系统，其本质就是用字母在字典序中的编号来代替该字母，即用 \(1∼26\) 代替 \(a∼z\)。

例如，单词 code，c 是第 \(3\) 个字母，o 是第 \(15\) 个字母，d 是第 \(4\) 个字母，e 是第 \(5\) 个字母，因此 code 经过加密后，得到的密文为 \(31545\)。

但是小猴发现，这样加密后的信息，可能会有多种解读，密文为 \(31545\) 除了 code 还可以是 caede，因此在解密时，有两种可能性。

现在，小猴给你一串密文，请你帮助小猴计算出所有可能的明文的种数对 \(10^9+7\) 取模。

【输入】

输入共一行，一串数字表示密文，保证一定有解。

【输出】

输出共一行，一个正整数表示答案。

【输入样例】

【输出样例】

【核心思想】

问题分析：给定一个数字密文串 \(s\)，每个数字可以单独翻译为对应字母（\(1 \to a, 2 \to b, \ldots, 9 \to i\)），或者与前一个数字组合成两位数翻译（\(10 \to j, 11 \to k, \ldots, 26 \to z\)）。求所有可能的解密方式数，结果对 \(10^9+7\) 取模。这是一个线性动态规划问题，类似于经典的解码方法问题。
算法选择：
- 动态规划（DP）：\(dp[i]\) 表示前 \(i\) 个字符的解密方式数
- 状态转移：根据当前字符是否为 \(0\) 以及能否与前一个字符组合，分情况讨论
关键步骤：
- 将输入数字转为字符串 \(s\)，下标从 \(1\) 开始
- 初始化：\(dp[0] = 1\)（空字符串有 \(1\) 种解密方式），\(dp[1] = 1\)（第一个字符单独解密）
- 状态转移（从 \(i = 2\) 到 \(n\)）：
  - 若 \(s[i] = '0'\)：当前字符必须与前一个组合，且前一个必须是 \('1'\) 或 \('2'\)（组成 \(10\) 或 \(20\)）
    - \(dp[i] = dp[i-2]\)（只能组合解密）
  - 若能组合成 \(10\)-\(26\)（\(s[i-1] = '1'\)，或 \(s[i-1] = '2'\) 且 \(s[i] \leq '6'\)）：
    - \(dp[i] = (dp[i-1] + dp[i-2]) \mod MOD\)
    - \(dp[i-1]\)：\(s[i]\) 单独解密的方式数
    - \(dp[i-2]\)：\(s[i-1]\) 和 \(s[i]\) 组合解密的方式数
  - 若不能组合：\(dp[i] = dp[i-1]\)（只能单独解密）
- 输出 \(dp[n]\) 作为答案
时间/空间复杂度：
- 时间复杂度：\(O(n)\)，只需遍历字符串一次
- 空间复杂度：\(O(n)\)，使用 \(dp\) 数组（可优化至 \(O(1)\)，只保留 \(dp[i-1]\) 和 \(dp[i-2]\)）
线性DP与含约束递推的核心思想：
- 最优子结构：前 \(i\) 个字符的解密数只与前 \(i-1\) 和 \(i-2\) 个字符有关
- 特殊约束处理：字符 \('0'\) 不能单独解密，必须与前一个组合成 \(10\) 或 \(20\)
- 状态转移分情况：根据当前字符的值和能否组合，决定转移方式
- 取模运算：结果可能很大，每一步都要对 \(10^9+7\) 取模防止溢出
- 适用于字符串解码、密码破解、组合计数等场景

【算法标签】

线性DP-一维

【代码详解】

#include<iostream>
#include<algorithm>
using namespace std;const int MOD = 1e9 + 7;  // 模数
string s;  // 输入的数字字符串
int n, dp[100005];  // n: 字符串长度，dp: 动态规划数组int main()
{cin >> s;  // 读入数字字符串n = s.size();  // 获取字符串长度s = ' ' + s;  // 在字符串前加一个空格，使下标从1开始dp[0] = dp[1] = 1;  // 初始化动态规划数组// dp[0] = 1: 空字符串有1种解码方式// dp[1] = 1: 第一个字符单独解码有1种方式（假设不是'0'）for (int i = 2; i <= n; i++){if (s[i] == '0')  // 如果当前字符是'0'{// 如果当前字符是'0'，它必须和前一个字符组合// 且前一个字符只能是'1'或'2'，否则无法解码// 解码方式数等于dp[i-2]dp[i] = dp[i - 2];}else if (s[i - 1] == '1' || s[i - 1] == '2' && s[i] <= '6'){// 如果前两个字符能组成10-26（除了20），则有两种解码方式：// 1. 当前字符单独解码：dp[i-1]种方式// 2. 前两个字符一起解码：dp[i-2]种方式dp[i] = (dp[i - 1] + dp[i - 2]) % MOD;}else{// 如果前两个字符不能组成有效数字，则当前字符必须单独解码dp[i] = dp[i - 1];}// cout<<dp[i]<<' ';  // 调试输出}cout << dp[n];  // 输出整个字符串的解码方式总数return 0;
}

【运行结果】