哈希算法题目：单词规律 题目描述 给定一种规律 pattern 和一个字符串 s ，判断 s 是否遵循相同的规律。这里的遵循规律是指： pattern 中的每个字母对应一个 s 中被空格分割的单词。 每个字母都必须对应一个唯一的单词，且每个单词也必须对应一个唯一的字母（即双射关系）。 如果 pattern 和 s 的长度不匹配（例如 pattern 有 k 个字母，但 s 分割后单词数不等于 k ），直接返回 false 。 示例 输入： pattern = "abba" , s = "dog cat cat dog" 输出： true （解释：a → dog, b → cat，且反向映射也一致） 输入： pattern = "abba" , s = "dog cat cat fish" 输出： false （b 对应 cat，但最后一个单词 fish 应被 a 映射，实际 a 已映射 dog） 输入： pattern = "aaaa" , s = "dog dog dog dog" 输出： true （所有 a 映射同一单词） 输入： pattern = "abba" , s = "dog dog dog dog" 输出： false （a 和 b 都试图映射 dog，违反唯一性） 解题过程 步骤 1：问题拆解 将字符串 s 按空格分割成单词数组 words 。 检查 pattern 长度是否等于 words 长度，若不相等则直接返回 false 。 需要建立两个映射关系： char_to_word ：从 pattern 中的字符到 words 中单词的映射。 word_to_char ：从单词到字符的反向映射（确保唯一性）。 遍历 pattern 的每个字符，同时用索引获取对应单词，验证双射关系是否一致。 步骤 2：建立映射表 使用哈希表（字典）存储映射： char_to_word ：键为字符，值为单词。 word_to_char ：键为单词，值为字符。 为什么需要两个表？ 例如 pattern = "abba" , s = "dog dog dog dog" ： 仅用 char_to_word 时，a → dog 和 b → dog 不会冲突（因为不同键可存相同值），但反过来 dog 会同时映射 a 和 b，违反唯一性。用 word_to_char 可检测此冲突。 步骤 3：遍历验证 遍历 pattern 的索引 i ： 当前字符 ch = pattern[i] ，对应单词 word = words[i] 。 检查 char_to_word 中是否已存在 ch 的映射： 若存在，且已映射的单词不等于当前 word ，返回 false 。 检查 word_to_char 中是否已存在 word 的映射： 若存在，且已映射的字符不等于当前 ch ，返回 false 。 若均未出现冲突，将 ch → word 和 word → ch 分别加入两个哈希表。 遍历完成后返回 true 。 步骤 4：举例说明 以 pattern = "abba" , s = "dog cat cat dog" 为例： 分割 words = ["dog", "cat", "cat", "dog"] 。 i=0: ch=a, word=dog 两个表均无记录，插入 a→dog 和 dog→a 。 i=1: ch=b, word=cat 无冲突，插入 b→cat 和 cat→b 。 i=2: ch=b, word=cat char_to_word[b] 存在且等于 cat，一致； word_to_char[cat] 存在且等于 b，一致。 i=3: ch=a, word=dog char_to_word[a] 存在且等于 dog，一致； word_to_char[dog] 存在且等于 a，一致。 遍历结束，返回 true 。 步骤 5：边界情况 pattern 和 words 长度不同：在步骤 1 直接判断。 所有字符相同且单词相同：如 "aaa" 和 "dog dog dog" ，双射仍成立。 字符不同但单词相同：如 "ab" 和 "dog dog" ，在 word_to_char 中会检测到 dog 已映射 a，但当前 ch=b 冲突。 总结 本题核心是通过两个哈希表维护双射关系，确保字符与单词的一一对应。时间复杂度为 O(n)，空间复杂度为 O(n)（存储映射表）。