题目描述与示例
题目描述
给定一段”密文”字符串s，其中字符都是经过”密码本”映射的，现需要将”密文”解密并且输出。
映射的规则 ："a-i"分别用"1-9"表示，"j-z" 分别用"10*-26*"表示
约束：映射始终唯一
输入描述
“密文”字符串
输出描述
明文字符串
补充说明
翻译后的文本的长度在100以内
示例一
输入
20*19*20*
输出
tst
示例二
输入
12320*12319*20*
输出
abctabcst
解题思路
元素映射
涉及元素一一映射的关系，构建从数字到字母的映射这件事，很容易想到应该使用哈希表来解决。
为了构建数字和字母之间的映射，可以使用ASCII码值来完成。使用ord("a")可以计算得到字符"a"的ASCII码值，选定数字i的范围为[1, 26]，则ord("a")+i-1可以得到所有小写字母的ASCII码值，再使用chr()内置函数将ASCII码值转换回小写字母，即chr(ord("a")+i-1)。故构建映射关系哈希表的代码为
dic = {str(i): chr(ord("a") + i - 1) for i in range(1, 27)}
两位数的处理
另外，本题所给密码字符串中，两位数（10-26）的后面都会带一个*，而一位数（1-9）的后面不带*，我们必须把这两种情况区分开来。
如果我们从头到尾地遍历原字符串s，每次遇到一个*号，则说明此时*号前面的两个字符需要合并在一起，视为一个两位数来处理。
很显然，只有在遇到*号的时候，才需要去查看刚刚最新遇到的两个数字字符，这是一种后进先出的思路，很显然可以使用栈来处理这个过程。其过程如下
stack = list()
for ch in s:
if ch == "*":
digit_1 = stack.pop()
digit_10 = stack.pop()
stack.append(digit_10 + digit_1)
else:
stack.append(ch)
退出循环后，栈中储存了若干个数字字符串（有一位数也有两位数），再将这些数字字符串传入哈希表中进行从数字到字母的映射，再合并为一个字符串输出即为答案。代码如下
print("".join(dic[num_str] for num_str in stack))
代码
Python
# 题目：【哈希表】2023C-密码解密
# 分值：200
# 作者：许老师-闭着眼睛学数理化
# 算法：栈，哈希表
# 代码看不懂的地方，请直接在群上提问
# 构建数字和字母之间的映射关系
dic = {str(i): chr(ord("a") + i - 1) for i in range(1, 27)}
# 输入字符串
s = input()
# 构建一个栈
stack = list()
# 遍历s中所有字符
for ch in s:
# 如果是*号，说明*前面的两个数字要合并为一个两位数一起考虑
if ch == "*":
# 弹出栈顶两个元素，分别是个位和十位的字符串
# 先弹出个位，再弹出10位
digit_1 = stack.pop()
digit_10 = stack.pop()
# 将合并后的两位数重新压回栈顶
stack.append(digit_10 + digit_1)
# 如果不是*号，而是数字，则直接入栈
else:
stack.append(ch)
# 最后栈中的所有元素即为数字字符串，使用dic进行从数字到字母的映射之后再合并即可
print("".join(dic[num_str] for num_str in stack))
Java
import java.util.HashMap;
import java.util.Scanner;
import java.util.Stack;
public class Main {
public static void main(String[] args) {
// 构建数字和字母之间的映射关系
HashMap<String, Character> dic = new HashMap<>();
for (int i = 1; i <= 26; i++) {
dic.put(Integer.toString(i), (char) ('a' + i - 1));
}
Scanner scanner = new Scanner(System.in);
String s = scanner.nextLine();
// 构建一个栈
Stack<String> stack = new Stack<>();
// 遍历s中所有字符
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
// 如果是*号，说明*前面的两个数字要合并为一个两位数一起考虑
if (ch == '*') {
// 弹出栈顶两个元素，分别是个位和十位的字符串
// 先弹出个位，再弹出10位
String digit_1 = stack.pop();
String digit_10 = stack.pop();
// 将合并后的两位数重新压回栈顶
stack.push(digit_10 + digit_1);
}
// 如果不是*号，而是数字，则直接入栈
else {
stack.push(Character.toString(ch));
}
}
// 最后栈中的所有元素即为数字字符串，使用dic进行从数字到字母的映射之后再合并即可
StringBuilder result = new StringBuilder();
while (!stack.isEmpty()) {
String numStr = stack.pop();
result.append(dic.get(numStr));
}
System.out.println(result.reverse().toString());
}
}
C++
“`C++
#include <iostream>
#include <unordered_map>
#include <stack>
using namespace std;
int main() {
// 构建数字和字母之间的映射关系
unordered_map<string, char> dic;
for (int i = 1; i <= 26; i++) {
dic[to_string(i)] = 'a' + i – 1;
}
<pre><code>string s;
cin >> s;
// 构建一个栈
stack<string> stack;
// 遍历s中所有字符
for (char ch : s) {
// 如果是*号，说明*前面的两个数字要合并为一个两位数一起考虑
if (ch == '*') {
// 弹出栈顶两个元素，分别是个位和十位的字符串
// 先弹出个位，再弹出10位
string digit_1 = stack.top();
stack.pop();
string digit_10 = stack.top();
stack.pop();
// 将合并后的两位数重新压回栈顶
stack.push(digit_10 + digit_1);
}
// 如果不是*号，而是数字，则直接入栈
else {
stack.push(string(1, ch));
}
}
// 最后栈中的所有元素即为数字字符串，使用dic进行从数字到字母的映射之后再合并即可
string result = "";
while (!stack.empty()) {
string numStr = stack.top();
stack.pop();
result = dic[numStr] + result;
}
// 输出结果
cout << result << endl;
return 0;
</code></pre>
}
“`
时空复杂度
时间复杂度：O(N)。需要一次遍历字符串s
空间复杂度：O(N)。哈希表所占空间，长度为26，可视为常数级别空间；栈所占空间最大为N。
说明
华为OD机试有三道题⽬，第⼀道和第⼆道属于简单或中等题，分值为 100 分，第三道为中等或困难题，分值为 200分，总分为 400 分。
机试分数越⾼评级越⾼，⼯资也就越⾼。
关于华为 OD 机试更加详细的介绍可以查看这篇⽂章：华为OD机考须知
关于机考题目汇总可以看这篇文章：华为OD机试真题 2023 A+B+C+D卷 + 2024新卷（Python&Java&C++）⽬录汇总（每⽇更新）
