LeetCode 290. 单词规律：多种解法与性能对比

LeetCode 290. 单词规律

给定一种规律 pattern 和一个字符串 s，判断 s 是否遵循相同的规律。

这里的 遵循 指完全匹配，例如，pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向的一一对应关系。

示例

示例 1: 输入：pattern = "abba", s = "dog cat cat dog" 输出：true

示例 2: 输入：pattern = "abba", s = "dog cat cat fish" 输出：false

示例 3: 输入：pattern = "aaaa", s = "dog cat cat dog" 输出：false

提示

• 1 <= pattern.length <= 300
• pattern 只包含小写英文字母
• 1 <= s.length <= 3000
• s 只包含小写英文字母和空格 ' '
• s 不包含 前导或尾随空格
• s 中每个单词都由单个空格分隔

---

解法一：双向哈希表法

解题思路

核心方法：双向哈希表映射法，通过两个 HashMap 分别维护 pattern 字符→s 单词 和 s 单词→pattern 字符 的双向唯一映射关系，确保'相同字符映射唯一单词'且'不同字符不映射到同一单词'，逻辑严谨且能完全满足'一一对应'的核心约束。

核心逻辑拆解

判断单词规律的核心是'字符与单词的双向唯一绑定'：

1. 前置校验：将 s 按空格分割为单词数组，若数组长度与 pattern 长度不一致，直接返回 false（字符数和单词数不匹配，无法一一对应）；
2. 正向约束：pattern 中的同一个字符，必须始终映射到 s 中的同一个单词（比如 pattern 的 'a' 不能既映射到 'dog' 又映射到 'cat'）；
3. 反向约束：s 中的同一个单词，只能被 pattern 中的一个字符映射（比如 pattern 的 'a' 和 'b' 不能同时映射到 'dog'）；
4. 双 Map 维护映射：
   • map：key 为 pattern 的字符，value 为 s 的单词（字符→单词）；
   • map2：key 为 s 的单词，value 为 pattern 的字符（单词→字符）；
5. 遍历验证：
   • 若字符已在 map 中，检查映射的单词是否与当前单词一致，不一致则返回 false；
   • 若字符不在 map 中，检查当前单词是否已被其他字符映射（在 map2 中），若已映射则返回 false；
   • 若都满足，将字符→单词、单词→字符分别存入两个 Map；
6. 遍历完成后返回 true。

性能说明

• 时间复杂度：O(n)（n 为 pattern 长度，分割字符串 O(m) + 遍历 O(n)，m 为 s 长度，整体仍为线性）；
• 空间复杂度：O(k)（k 为不同字符/单词的数量，最多等于 长度）；