HJ36. 字符串加密
题目描述
给定密钥底串 key 和明文：
- 将 key 去重（保留每个字母第一次出现），得到 key 去重后的字符串；
- 从 'a' 开始，把 26 个字母中 key 未出现过的字母依次补在末尾，构成完整的新字母表；
- 加密：明文中的每个字母，替换为新字母表中"相同位置"的字母。
输入格式
- 第 1 行：key（仅小写字母）
- 第 2 行：明文（仅小写字母）
输出格式
- 加密后的密文。
示例
示例 1
输入：
trailblazers
attackatdawn
输出：
tpptadtpitvh
说明：
key trailblazers 去重得 trailbzes，补全 26 字母得到新字母表 trailbzescdfghjkmnopquvwxy，明文按位置替换得 tpptadtpitvh。
示例 2
输入：
nihao
ni
输出：
le
解题思路
第一步：理解问题本质
先用 key 构建一张"新字母表"（key 去重 + 补全缺失字母），再按原字母在新字母表中的位置替换明文。
第二步：暴力解法（逐个字符构建）
手动构建新字母表，逐个字符处理明文替换。
问题：去重和补全逻辑需要仔细维护 seen 集合，容易重复加入字母。
第三步：优化解法（构建新字母表）
构建流程：
- 遍历 key，用
seen集合记录已出现字母，按顺序加入alpha列表（去重）。 - 遍历
a-z，把未在seen中的字母依次补到末尾。
def build_alphabet(key: str) -> str:
seen = set()
alpha = []
for ch in key:
if ch not in seen:
seen.add(ch)
alpha.append(ch)
for ch in "abcdefghijklmnopqrstuvwxyz":
if ch not in seen:
alpha.append(ch)
return ''.join(alpha)
第四步：最优解法（查表替换）
对明文每个字符，用 table[ord(c)-ord('a')] 直接取新字母表中对应位置的字母。
result = ''.join(table[ord(c) - ord('a')] for c in plain)
完整代码实现
算法可视化 · 逐帧回放这道题的代码75 帧 · 录制输入
import sys
def build_alphabet(key: str) -> str:
"""构建新字母表：key 去重 + 补充缺失字母"""
seen = set()
alpha = []
for ch in key:
if ch not in seen:
seen.add(ch)
alpha.append(ch)
# 补充 a-z 中未出现的字母
for ch in "abcdefghijklmnopqrstuvwxyz":
if ch not in seen:
alpha.append(ch)
return ''.join(alpha)
def solve() -> None:
"""主求解函数"""
key = sys.stdin.readline().strip()
plain = sys.stdin.readline().strip()
table = build_alphabet(key)
result = ''.join(table[ord(c) - ord('a')] for c in plain)
print(result)
if __name__ == "__main__":
solve()
示例推演
以示例 1 为例：
构建新字母表： key = trailblazers
- 去重：依次遇到 t、r、a、i、l、b、z、e、s →
trailbzes（后面的 a、r 已出现跳过） - 补全 a-z 中未出现的字母：c、d、f、g、h、j、k、m、n、o、p、q、u、v、w、x、y
- 新字母表：
trailbzescdfghjkmnopquvwxy
加密明文 attackatdawn： 按位置替换
| 明文 | 位置 | 新字母表对应 | 密文 |
|---|---|---|---|
| a | 0 | t | t |
| t | 19 | p | p |
| t | 19 | p | p |
| a | 0 | t | t |
| c | 2 | a | a |
| k | 10 | d | d |
| a | 0 | t | t |
| t | 19 | p | p |
| d | 3 | i | i |
| a | 0 | t | t |
| w | 22 | v | v |
| n | 13 | h | h |
拼接结果：tpptadtpitvh。
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 逐个字符构建 | O(K+L) | O(26) | 需维护去重集合 |
| 构建表 + 查表 | O(K+L) | O(26) | 查表 O(1) |
K 为 key 长度，L 为明文长度
易错点总结
1. key 去重保留首次出现
去重必须保留每个字母第一次出现的位置和顺序，用 seen 集合判断是否已加入。
2. 补全缺失字母
补全的是 a-z 中 key 未出现过的字母，按字母表顺序，不能遗漏。
3. 新字母表长度
新字母表必须恰好 26 个字母，key 去重后补充的字母数 = 26 - 去重后 key 长度。
4. 按位置替换
明文替换用的是原字母在标准字母表中的位置（0-25），不是按字符查 key。
扩展思考
- 这类"自定义字母表替换"本质是建立一张一一映射的替换表，可用
str.translate或字典加速。 - 加密与解密方向相反，只需反转替换表即可实现解密。