P2820. 密码解密

解题思路

本题需要分两步走：对原字符串的预处理以及元素映射关系。

元素映射

涉及元素一一映射的关系，构建从数字到字母的映射这件事，很容易想到应该使用哈希表来解决。

为了构建数字和字母之间的映射，可以使用ASCII码值来完成。使用 ord("a") 可以计算得到字符 "a" 的 ASCII 码值，选定数字 i 的范围为 [1, 26]，则 ord("a") + i - 1 可以得到所有小写字母的 ASCII 码值，再使用 chr() 内置函数将 ASCII 码值转换回小写字母，即 chr(ord("a") + i - 1)。故构建映射关系哈希表的代码为：

两位数的处理

另外，本题所给密码字符串中，**两位数（10-26）的后面都会带一个 *，而一位数（1-9）的后面不带 ***，我们必须把这两种情况区分开来。

如果我们从头到尾地遍历原字符串 s，每次遇到一个 * 号，则说明此时 * 号前面的两个字符需要合并在一起，视为一个两位数来处理。

很显然，只有在遇到 * 号的时候，才需要去查看刚刚最新遇到的两个数字字符，这是一种后进先出的思路，很显然可以使用栈来处理这个过程。其过程如下：

退出循环后，栈中储存了若干个数字字符串（有一位数也有两位数），再将这些数字字符串传入哈希表中进行从数字到字母的映射，再合并为一个字符串输出即为答案。代码如下：

复杂度分析 设密文字符串 s 的长度为 n。构建 1 到 26 与字母的映射表是固定的 26 次操作，O(1)。主循环对 s 做单次遍历：普通数字字符直接入栈是 O(1)；遇到 "*" 弹出两个元素、合并后压回，也是 O(1)。扫描共 O(n)。最后把栈里的数字串逐个查表并 join 成结果，O(n)。总时间复杂度 O(n)，空间复杂度 O(n)（栈中最多存 n 个字符片段）。

边界与注意事项

• 题面约定映射始终唯一：一位数 1-9 后面不带 *，两位数 10-26 后面必带 *。正因如此，遇到 "*" 时栈顶一定恰好有两个待合并的数字字符，先弹出的是个位、后弹出的是十位，压回时要拼成"十位+个位"，顺序不能反。
• 如果密文全是一位数，循环不会触发合并分支，栈里就是逐字符的结果，逻辑自然退化成逐位查表。
• 映射表覆盖 1 到 26 全部取值，两位数合并后必落在 10 到 26 之间（题面编码规则保证），查表不会落空。
• C++ 版本用 stack 实现，栈是后进先出，最后要从栈顶往回拼接（代码用 result = dic[numStr] + result 前插）才能还原从左到右的原始顺序，这一点与 Python 版直接对 list 做 join 不同。