小杨的字典 题解

题目分析

本题要求实现一个简单的单词翻译程序。核心任务是从给定的字典中查找 A 语言单词，并替换为对应的 B 语言单词；若字典中不存在该单词，则替换为 UNK。文章中的单词由标点符号分隔，翻译时需要保留原文中的标点符号。

输入规模较小：字典最多 100 个条目，每个单词长度不超过 10，文章长度不超过 1000。因此直接模拟即可轻松通过。

解题思路

1. 建立字典
   使用哈希表（如 C++ 中的 map 或 unordered_map）存储 A→B 的映射关系，这样可以在 O(log N) 或平均 O(1) 的时间内完成单词查询。

2. 遍历文章，分离单词和标点
   文章由小写字母和若干标点符号组成。我们可以遍历字符串中的每个字符：

   • 若当前字符是小写字母（'a' ~ 'z'），将其追加到当前单词临时串 word 中。
   • 若当前字符是标点符号，则说明一个单词已经结束，此时：
     • 如果 word 非空，则在字典中查询该单词：找到则输出对应翻译，找不到则输出 UNK；
     • 输出该标点符号自身；
     • 清空 word，准备接收下一个单词。

3. 处理文章末尾的单词
   文章可能以单词结尾（末尾没有标点），为了统一处理，可以在文章字符串末尾人为添加一个非字母字符（例如换行符 \n）。这样当遍历到该字符时，会触发最后一次单词翻译，同时输出该字符（换行符不影响评测，但会多一个空行）。

算法说明

1. 读入整数 N，循环 N 次读入单词 A 和 B，存入 map<string, string>。
2. 读入整篇文章字符串 S。
3. 为了方便处理末尾单词，在 S 末尾追加一个非字母字符（如 '\n'）。
4. 遍历 S 的每一个字符：
   • 如果是字母 → 追加到 word；
   • 如果不是字母 → 处理 word（查字典并输出结果），然后输出该非字母字符，清空 word。

参考代码及解释

cpp
复制
1#include <iostream>
2#include <string>
3#include <map>
4using namespace std;
5
6int main() {
7    map<string, string> dict;
8    int N;
9    cin >> N;
10    // 读入字典
11    while (N--) {
12        string A, B;
13        cin >> A >> B;
14        dict[A] = B;   // 建立 A -> B 映射
15    }
16
17    string S, word = "";
18    cin >> S;
19    S += "\n";         // 在末尾添加一个非字母字符，保证最后一个单词能被处理
20
21    for (int i = 0; i < S.length(); i++) {
22        if (S[i] >= 'a' && S[i] <= 'z') {  // 是字母
23            word += S[i];
24        } else {                           // 是标点或换行符
25            if (word != "") {
26                if (dict.count(word))      // 字典中存在
27                    cout << dict[word];
28                else                       // 不存在，输出 UNK
29                    cout << "UNK";
30                word = "";                 // 清空，准备下一个单词
31            }
32            cout << S[i];                  // 输出标点符号自身
33        }
34    }
35    return 0;
36}

代码解释

• map<string, string> dict：存储 A 语言到 B 语言的映射，dict.count(word) 可以判断单词是否存在。
• S += "\n"：在文章末尾添加换行符，确保当文章以单词结尾时，该单词能在循环内被正常处理。
• 单词判断：通过 S[i] >= 'a' && S[i] <= 'z' 判断是否为字母，比使用 isalpha 更明确地区分字母和标点。
• 输出顺序：先输出翻译后的单词（或 UNK），再输出原标点符号，完全保留原文的标点结构。

时间复杂度分析

• 建立字典：O(N)，N ≤ 100，可以忽略。
• 翻译文章：遍历文章每个字符一次，共 O(|S|)，|S| ≤ 1000。
• 单词查询：使用 map 为 O(log N)，总复杂度 O(|S| log N)，在给定数据范围下瞬间完成。

空间复杂度：O(N) 用于存储字典，同样非常小。

注意事项

• 空单词不要处理：如果连续出现两个标点，word 为空，此时不要查询或输出任何翻译。
• 单词区分大小写：题目保证只包含小写字母，不需要额外转换。
• 最后多输出的一个换行符：由于我们在 S 末尾添加了 \n，程序会额外输出一个换行，但对于 OI 评测来说，行末换行通常不影响结果。如果不想多输出，可以采用另一种处理方式：在循环结束后单独判断 word 是否非空。