1. 题目背景解析
PAT乙级1033题是浙江大学计算机程序设计能力考试（Programming Ability Test）中的一道经典字符串处理题目。这类题目主要考察考生对基础编程概念的掌握程度和解决实际问题的能力。乙级考试作为PAT的初级难度，题目通常不会涉及复杂算法，但对编程基本功和细节处理能力要求较高。
在实际编程竞赛和面试中，字符串处理类题目出现频率极高。根据国内主流OJ平台统计，字符串相关题目占比超过35%，其中键盘输入模拟类题型约占15%。这道1033题正是典型的键盘输入模拟场景，非常贴近实际开发中可能遇到的字符过滤需求。
2. 题目需求分析
2.1 问题描述重述
题目给出两个字符串：
- 第一个字符串表示键盘上坏掉的按键（可能为空）
- 第二个字符串是需要输出的文本内容
要求根据坏键情况，输出实际能够打出的文本。这里有几个关键条件需要注意：
- 坏键以大写字母形式给出（但影响大小写两个版本）
- 上档键（Shift键）损坏会导致所有大写字母无法输出
- 题目保证输入中至少有一个有效字符
2.2 输入输出样例解析
以样例1为例：
code复制7+IE.
7_This_is_a_test.
坏键是"7+IE."，需要处理的文本是"7_This_is_a_test."。正确输出应该是：
code复制_hs_s_a_tst
这个样例验证了几个关键点：
- 数字键7被损坏，文本中的7被过滤
- '+'代表上档键损坏，导致所有大写字母无法输出（原文本中的T、I都被过滤）
- 下划线和小写字母正常输出
- 标点符号'.'在坏键中，但原文本中没有，不影响输出
3. 解题思路设计
3.1 核心算法选择
这道题适合采用哈希表（HashSet）辅助的线性扫描算法，时间复杂度O(n+m)，其中n和m分别是两个字符串的长度。具体步骤：
-
预处理坏键集合：
- 将每个坏键字符存入哈希集合
- 特别检查是否有'+'存在（表示上档键损坏）
-
遍历待处理文本：
- 对每个字符检查是否应该输出
- 需要同时检查字符本身及其大小写变体
- 上档键损坏时跳过所有大写字母
3.2 边界情况处理
实际编码时需要特别注意的边界情况：
- 坏键字符串可能为空（但题目保证至少有一个有效字符）
- 上档键损坏时对大小写字母的影响
- 同一个字母的大小写可能同时出现在坏键中
- 输出可能为空字符串（虽然题目保证至少一个有效字符）
4. 代码实现详解
4.1 C++实现版本
cpp复制#include <iostream>
#include <unordered_set>
#include <cctype>
using namespace std;
int main() {
string badKeys, text;
getline(cin, badKeys); // 使用getline读取可能包含空行的输入
getline(cin, text);
unordered_set<char> broken;
bool shiftBroken = false;
// 预处理坏键集合
for (char c : badKeys) {
if (c == '+') {
shiftBroken = true;
}
broken.insert(toupper(c));
}
// 处理文本
for (char c : text) {
if (broken.count(toupper(c))) {
continue; // 字符在坏键集合中
}
if (shiftBroken && isupper(c)) {
continue; // 上档键损坏且当前是大写字母
}
cout << c;
}
return 0;
}
4.2 Java实现版本
java复制import java.util.HashSet;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String badKeys = sc.nextLine();
String text = sc.nextLine();
HashSet<Character> broken = new HashSet<>();
boolean shiftBroken = false;
// 预处理坏键集合
for (int i = 0; i < badKeys.length(); i++) {
char c = badKeys.charAt(i);
if (c == '+') {
shiftBroken = true;
}
broken.add(Character.toUpperCase(c));
}
// 处理文本
StringBuilder result = new StringBuilder();
for (int i = 0; i < text.length(); i++) {
char c = text.charAt(i);
if (broken.contains(Character.toUpperCase(c))) {
continue;
}
if (shiftBroken && Character.isUpperCase(c)) {
continue;
}
result.append(c);
}
System.out.println(result.toString());
}
}
4.3 Python实现版本
python复制bad_keys = input().strip()
text = input().strip()
broken = set()
shift_broken = False
# 预处理坏键集合
for c in bad_keys:
if c == '+':
shift_broken = True
broken.add(c.upper())
# 处理文本
result = []
for c in text:
if c.upper() in broken:
continue
if shift_broken and c.isupper():
continue
result.append(c)
print(''.join(result))
5. 关键考点与技巧
5.1 字符处理要点
- 大小写统一处理：将字符统一转换为大写或小写进行比较，避免大小写敏感问题
- 上档键特殊处理：'+'字符需要单独判断，它影响所有大写字母的输出
- 空输入处理：虽然题目保证有有效输入，但实际编程时应考虑边界情况
5.2 性能优化技巧
- 使用哈希集合：HashSet的查找时间复杂度为O(1)，远优于数组遍历
- 提前处理坏键：预处理阶段建立好坏键集合，避免在文本处理时重复计算
- 字符串构建优化：在Java/Python中使用StringBuilder/列表拼接字符串，避免频繁创建新字符串
5.3 常见错误警示
- 未考虑上档键影响：忘记处理'+'导致的大写字母过滤不完整
- 大小写处理不当：直接比较字符而未统一大小写，导致漏判
- 输入读取问题：使用错误的输入方法（如cin>>）导致无法读取空行或空格
- 输出格式错误：多输出换行符或少输出字符，与样例不符
6. 测试用例设计
6.1 标准测试用例
| 输入 | 预期输出 | 说明 |
|---|---|---|
| 7+IE. 7_This_is_a_test. |
_hs_s_a_tst | 基本功能测试 |
| aeiou AEIOUaeiou |
全部小写元音损坏 | |
| + AbCdEfG |
bcdfg | 仅上档键损坏 |
| 0 1020304050 |
12345 | 数字键损坏 |
6.2 边界测试用例
| 输入 | 预期输出 | 说明 |
|---|---|---|
| (空行) Hello |
Hello | 无坏键情况 |
| A a |
大小写同时被过滤 | |
| . ...Hello... |
Hello | 标点符号过滤 |
7. 复杂度分析与优化
7.1 时间复杂度
算法的时间复杂度主要由两部分组成：
- 预处理坏键集合：O(m)，m为坏键字符串长度
- 处理文本字符串：O(n)，n为文本长度
总体时间复杂度为O(m+n)，是线性复杂度，对于PAT乙级题目完全足够。
7.2 空间复杂度
使用了一个哈希集合存储坏键，空间复杂度为O(m)。在实际应用中，由于键盘按键数量有限（ASCII字符最多128个），空间消耗可以视为常数级O(1)。
7.3 进一步优化方向
- 位图法：使用位向量代替哈希集合，减少内存使用（适用于固定字符集）
- 并行处理：对于超长文本，可以分段并行处理
- 预处理优化：如果坏键集合固定，可以预先计算并缓存
8. 实际应用扩展
8.1 类似场景应用
这种字符过滤算法在实际开发中有广泛应用：
- 敏感词过滤系统
- 输入校验和清理
- 搜索引擎的关键词处理
- 代码编辑器的语法高亮预处理
8.2 工程实践建议
在实际项目中实现类似功能时，建议：
- 使用更完整的字符编码处理（如支持Unicode）
- 添加白名单和黑名单双重机制
- 考虑性能优化，特别是处理大规模文本时
- 编写详尽的单元测试，覆盖各种边界情况
8.3 题目变种思考
可以尝试解决以下变种题目提升能力：
- 多键盘布局支持（如QWERTY和DVORAK）
- 考虑按键粘滞情况（偶尔能打出字符）
- 添加自动更正功能（用相似字符替换坏键）
- 处理组合键和功能键（如Ctrl+C等）