GESP 题解库 / 4 级题解 / [GESP202312 四级] 小杨的字典 · 第 17 / 25 题
GESP202312 四级 · B3927 · 简单

小杨的字典

按字典把文章中的单词替换成译文,标点原样保留,未收录的单词替换为 UNK。

📊
N ≤ 100
词典条目
🔤
文章 ≤ 1000
文章长度
⚡
O(文章长度)
时间复杂度
🎯
逐字符扫描 + 查表
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

文章由标点符号和单词组成,每个单词之间必定由至少一个标点符号分割。

请把文章中的所有 A 语言单词替换成字典中对应的 B 语言翻译;若单词不在字典中,替换成大写的 UNK。标点符号原样保留。

例:字典含 abc → a、d → def,则 abc.d.d.abc.abcd. 翻译为 a.def.def.a.UNK.

💡
人话翻译:标点是"分隔符",夹在两个标点之间的连续字母就是一个"完整单词"。关键点:必须完整匹配整个单词——例子里的 abcd 虽然以 abc 开头,但它本身不在字典里,所以要换成 UNK。

🔍 关键词提取

逐字符扫描单词边界查表替换标点保留

已知条件

项目说明
输入第一行 N;随后 N 行每行 A、B 两个单词;最后一行文章 S
输出翻译后的文章(一行)
数据范围N ≤ 100,S 长度 ≤ 1000
字符集S 只含小写字母和标点(不含空格)
单词定义被标点分隔的连续小写字母序列

需要解决的问题

02
思维导图
整理解题思路的全貌
📖 逐字符扫描 + 结算单词
📥 读入
N 条词典
用 map 存 A→B
读入文章 S
用 getline 或 cin
🔍 扫描
cur 累积当前单词
遇字母 → 追加到 cur
遇标点 → 先结算 cur,再输出该标点
标点原样输出
✅ 结算
cur 为空 → 什么都不做
cur 在字典中 → 输出译文
cur 不在字典中 → 输出 UNK
然后清空 cur
⚠️ 易错点
结尾残留单词未结算
把 abcd 误用 abc 的前缀匹配
标点被吞掉
连续标点处理错误
03
样例手算推导
样例文章的逐字符翻译过程

🧮 样例:abc.d.d.abc.abcd. 的翻译

字典:abc → a、d → def。我们对文章逐字符扫描。

1
第 1 段:abc

读到 a、b、c → cur = "abc"

读到 '.' → 结算 cur:"abc" 在字典中 → 输出 "a",再输出 '.'

cur 清空

已输出 "a."

2
第 2 段:d

读到 d → cur = "d"

读到 '.' → 结算:"d" 在字典中 → 输出 "def",再输出 '.'

已输出 "a.def."

3
第 3 段:d

同上 → 输出 "def."

已输出 "a.def.def."

4
第 4 段:abc

读出 "abc" → 在字典中 → 输出 "a" 和 '.'

已输出 "a.def.def.a."

5
第 5 段:abcd

读出 完整的 "abcd"(四个字母)

查字典:没有 "abcd" 这个条目

⚠️ 注意不能因为"以 abc 开头"就用 abc 的译文

正确做法:输出 "UNK",再输出 '.'

✅ 最终 "a.def.def.a.UNK."

📊 逐段对照表

原文单词是否在字典中译文
abc✅ 在(→ a)a
d✅ 在(→ def)def
d✅ 在(→ def)def
abc✅ 在(→ a)a
abcd❌ 不在UNK
🔑
本题最核心的坑:必须"完整匹配整个单词"。很多同学会想"abcd 以 abc 开头,查得到就用 abc 的译文"——这是前缀匹配,本题要求的是完全相等。所以扫描时要把连续的字母全部累积完,遇到标点再整体查表。

🧮 连续标点怎么处理

题目说"每个单词之间至少一个标点",所以可能出现连续多个标点。

原文片段处理过程输出
abc..d结算 abc → a;遇到两个 '.' 都原样输出;再结算 da..def
.abc开头就是 '.',此时 cur 为空 → 只输出 '.';再结算 abc.a
abc.结算 abc → a,输出 '.';扫描结束,cur 已空a.
⚠️
注意 cur 为空时不要输出任何东西:遇到标点时如果 cur 是空的,说明这之前已经有标点(或文章开头就是标点),此时只能输出标点本身,不能输出 UNK。否则连续标点会被翻译成一堆 UNK。
04
解法对比
逐字符扫描 vs 用字符串流切分

⚔️ 解法对比

🟢 逐字符扫描(推荐) 推荐

用一个游标累积单词,遇标点就结算并输出标点

  • 时间 O(文章长度)
  • 一趟扫描完成
  • 标点自动原样保留
  • 代码 20 行
💡
实现结构:for (每个字符 c) { if (是字母) cur += c; else { 结算 cur; 输出 c; } }最后务必再结算一次,处理结尾残留的单词。

🟠 用 stringstream 按标点切分

把标点统一替换成空格,再用流提取单词

  • 需要额外保存标点位置
  • 标点顺序容易错乱
  • 实现更绕
  • 不推荐
⚠️
为什么不好:本题要求标点原样保留且位置不变,用流切分会丢掉标点信息,还得另外记住它们在哪儿——不如逐字符扫描直接、可靠。

📈 性能对比

方案代码量标点处理
逐字符扫描约 20 行自然保留
流式切分约 35 行需要额外记录位置
05
算法流程图
扫描到标点就结算单词
开始读入 N 条词典(存入 map);读入文章 Scur = "";按顺序取 S 中每个字符 cc 是小写字母吗?是 ✓cur 追加 c否 ✗结算 cur,再输出标点 cS 中还有字符吗?扫描结束:若 cur 非空,再结算一次结束还有字符 → 取下一个
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

📖 字典翻译器

第一行输入词典条目数 N,随后 N 行 A B,最后一行输入文章。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    scanf("%d", &n);

    map<string, string> dict;
    for (int i = 0; i < n; i++) {
        string a, b;
        cin >> a >> b;
        dict[a] = b;
    }

    string s;
    cin >> s;                       // 文章不含空格,可直接读

    string cur = "", ans = "";

    // 结算当前单词
    auto settle = [&]() {
        if (cur.empty()) return;
        auto it = dict.find(cur);
        ans += (it != dict.end() ? it->second : string("UNK"));
        cur = "";
    };

    for (char c : s) {
        if (c >= 'a' && c <= 'z') {
            cur += c;               // 累积单词
        } else {
            settle();               // 先结算单词
            ans += c;               // 标点原样输出
        }
    }
    settle();                       // 别忘了结尾可能还有单词

    printf("%s\n", ans.c_str());
    return 0;
}
🔑
为什么末尾必须再 settle() 一次?如果文章以单词结尾(例如 abc.d),那么最后那个 d 会被累积到 cur,但后面没有标点来触发结算——循环结束后必须补一次,否则最后一个单词会被丢掉。

📖 关键几行怎么看

代码作用为什么这样写
if (c >= 'a' && c <= 'z')判断字母文章只含字母和标点,非字母即标点
cur += c累积单词把连续字母拼成完整单词
settle(); ans += c;遇标点先结算单词,再输出标点,顺序不能反
dict.find(cur)查字典用 find 判断是否存在,避免误插
⚠️
三个坑:① 循环结束忘记 settle(),丢掉末尾单词;② 用前缀匹配(如把 abcd 用 abc 翻译),必须完整相等;③ cur 为空时也输出 UNK,导致连续标点被错误替换。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
2 / abc a / d def / abc.d.d.abc.abcd.a.def.def.a.UNK.题面样例
1 / a x / ax文章只有一个单词
1 / a x / ..a..x开头连续标点原样保留
1 / a x / a..x..结尾连续标点原样保留
1 / a x / a 且 a.ax.x中间单标点
1 / abc y / abcdUNK完整匹配:abcd 不在字典中
✅
自查清单:① 末尾结算了吗?② 用的是完整匹配吗?③ cur 为空时没输出东西吧?

🚨 易错点清单

⚠️
循环结束忘记结算:文章以单词结尾时,最后那个单词会丢失。
⚠️
前缀匹配:abcd 必须以整个单词去查字典,不能因为以 abc 开头就用 abc 的译文。
⚠️
cur 为空时输出 UNK:遇到标点时若 cur 为空,只输出标点本身。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(S + 单词数 × log N)
空间复杂度
O(N + S)
S 长度
≤ 1000
N 最大
100

时间怎么算的?

空间都用在哪?

需要存词典(N 条)和结果字符串。

✅ S ≤ 1000,规模极小,任何实现都瞬间完成。这题考的是"单词边界"的处理是否周全。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 用 lambda 封装"结算"逻辑(C++11 起)
auto settle = [&]() {
    if (cur.empty()) return;
    auto it = dict.find(cur);
    ans += (it != dict.end() ? it->second : string("UNK"));
    cur = "";
};

// 判断字符类别
bool isLetter(char c) { return c >= 'a' && c <= 'z'; }

// 若标点集合已知,也可以显式列出
// 本题文章中只有字母和标点,所以"非字母即标点"最省事

// 读入文章:不含空格用 cin >> s;含空格用 getline(cin, s)

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
单词边界遇分隔符才结算文本分词、tokenizer、词法分析
完整匹配用 map/哈希表精确查所有需要精确查找的场景
末尾补结算循环外再处理一次所有"分隔符驱动"的扫描算法
🌟
思考题:如果题目改成"标点符号也要翻译"(比如 . 翻译成 。),代码要改哪里?(提示:只需在遇到标点那个分支里,先查一次"标点字典"再输出。这说明当前的骨架——"遇字母累积、遇分隔符结算"——可以很容易地扩展。)