你好，各位竞赛同学！今天我们来学习一道字符串处理与双向映射（双射）判定的基础练习题。在 NOI 竞赛中，字符串模拟与哈希表的灵活运用是必须掌握的基本功。

我们今天要讨论的题目是：Word Pattern (单词规律)。

---

一、 题目描述 (NOI 竞赛风格)

题目名称：Word Pattern 时间限制：1.0s 内存限制：128MB

【问题描述】 给定一组规律 pattern 和一个字符串 s，请判断 s 是否遵循相同的规律。 这里的“遵循”是指完全匹配，即在规律 pattern 中的每个字母和字符串 s 中的每个非空单词之间存在着**双射（Bijection）**关系。

1. pattern 中的每个字符必须恰好对应 s 中的一个单词。
2. s 中的每个单词必须恰好对应 pattern 中的一个字符。
3. 这种映射关系必须是一一对应的，且不可改变。

【输入格式】 输入共两行。 第一行包含一个字符串 pattern，仅包含小写英文字母。 第二行包含一个字符串 s，包含小写英文字母和空格。单词之间由单个空格分隔，输入不含前导或尾随空格。

【输出格式】 如果符合规律，输出 true，否则输出 false。

【样例输入 #1】

abba
dog cat cat dog

【样例输出 #1】

true

【样例输入 #2】

abba
dog cat cat fish

【样例输出 #2】

false

【数据范围】

• $1 \le \text{pattern.length} \le 300$
• $1 \le \text{s.length} \le 3000$
• s 只包含小写英文字母和空格 ' '。

---

二、 预备知识点

1. 字符串拆分 (Tokenization)：如何高效地从长字符串中提取被空格分隔的单词。
2. 哈希表 (Hash Map)：建立 char 到 string 以及 string 到 char 的双向映射。
3. 双射关系 (Bijection)：理解 A 映射到 B 的同时，B 也必须唯一映射到 A。

---

三、 启发式推理过程（草稿纸上的步骤）

请大家拿出草稿纸，我们模拟一遍思维过程：

1. 具象化拆解

面对输入 abba 和 dog cat cat dog，我们第一步要做什么？

• 动作：把 s 切开。
• 结果：我们得到一个单词序列：["dog", "cat", "cat", "dog"]。
• 检查：规律有 4 个字母，单词有 4 个。如果数量不等（例如规律 4 个，单词 5 个），直接判定失败。

2. 建立档案（双向核对）

我们需要保证“双向奔赴”。

• 尝试单向映射的风险：如果 a -> dog, b -> dog。从规律看没问题，但从单词看，dog 对应了两个不同的规律字符，这违反了双射原则。

3. 模拟匹配（草稿记录）

以规律 abba 为例：

1. 读取 a 和 dog：
   • 查档案：a 有人领了吗？没有。dog 有人领了吗？没有。
   • 记录：a <-> dog。
2. 读取 b 和 cat：
   • 查档案：b 和 cat 都是新人。
   • 记录：b <-> cat。
3. 读取 b 和 cat：
   • 查档案：b 已经心有所属（cat）。核对当前单词：是 cat，一致，通过。
4. 读取 a 和 dog：
   • 查档案：a 已经心有所属（dog）。核对当前单词：是 dog，一致，通过。

结论：全部通过，结果为 true。

---

四、 逻辑流程图 (Mermaid 语法避障版)

graph TD
    Start(开始) --> Input(读取 pattern 和字符串 s)
    Input --> Split(拆分 s 为单词列表 words)
    Split --> CountCheck{pattern 长度是否等于 words 长度}
    CountCheck -- 否 --> ReturnFalse(返回 false)
    CountCheck -- 是 --> LoopStart(遍历索引 i 从 0 到 N 减 1)
    LoopStart --> GetVar(取出字符 p_i 和单词 w_i)
    GetVar --> MapCheck1{p_i 已经在映射中}
    MapCheck1 -- 是 --> ValCheck1{映射值是否等于 w_i}
    ValCheck1 -- 否 --> ReturnFalse
    ValCheck1 -- 是 --> MapCheck2
    MapCheck1 -- 否 --> MapCheck2{w_i 已经在反向映射中}
    MapCheck2 -- 是 --> ValCheck2{反向映射值是否等于 p_i}
    ValCheck2 -- 否 --> ReturnFalse
    ValCheck2 -- 是 --> Next
    MapCheck2 -- 否 --> Record(在两个映射表中记录 p_i 与 w_i 的关系)
    Record --> Next(进入下一轮循环)
    Next --> LoopEnd{循环是否结束}
    LoopEnd -- 否 --> LoopStart
    LoopEnd -- 是 --> ReturnTrue(返回 true)
    ReturnFalse --> End(结束)
    ReturnTrue --> End

---

五、 时间与空间复杂度分析

1. 时间复杂度：

   • 拆分字符串：需要遍历一次 s，复杂度 $O(M)$，$M$ 是 s 的长度。
   • 哈希表操作：遍历 pattern 长度 $N$ 次。每次插入和查找字符串哈希表的复杂度取决于单词平均长度 $L$。
   • 总计：$O(M + N \times L)$。由于 $N \times L$ 的量级大约等于 $M$，故总体为 $O(M)$。在 $3000$ 的规模下，运行时间远低于 1s。

2. 空间复杂度：

   • 需要存储单词列表和两个哈希表。
   • 总计：$O(M + N)$，主要取决于字符串存储空间。

优化建议：

• 在 C++ 中，使用 std::stringstream 可以方便地拆分单词，但在超大规模数据下，手动双指针遍历 s 寻找空格会更快。
• 使用 std::unordered_map 替代 std::map 可以获得更好的平均查询常数。

---

六、 读题关键词提取（避坑指南）

在处理字符串匹配类题目时，请圈出以下关键词：

1. “一一对应” / “双射” (Bijection)：这意味着你必须检查两个方向的唯一性（字符到单词，单词到字符）。
2. “非空单词”：注意处理空格，确保拆分后的内容有效。
3. “规律长度与字符串规模”：如果长度不等，哈希表逻辑之前就要特判。
4. “字符集范围”：本题仅小写字母，这意味着字符映射可以用 string map[26] 数组来优化常数。

教练提示：在 NOI 比赛中，字符串处理题往往隐藏着特殊情况（如 s 比 pattern 长很多或短很多）。先写长度判断，再写逻辑，能帮你规避 50% 的低级错误。加油！