华为 OD 训练营 · 题解精讲
LC290. 单词规律
LC290. 单词规律
题目描述
给定一种规律 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 中每个单词都被 单个空格 分隔
题目解析
解题思路
本题要求判断字符串 s 中的单词序列是否与 pattern 的字符序列构成一一对应的双射关系。参考代码采用双哈希表方法，分别建立 pattern 字符到单词、单词到 pattern 字符的映射，同步检查双向映射是否一致。
核心思想：遍历 pattern 的每个字符和 s 的每个单词，维护两个字典：
dic1：单词 → 字符映射dic2：字符 → 单词映射
若发现任一方向映射冲突（即已存在的映射与当前对应关系不符），则返回 False。
关键步骤
1. 预处理：将 s 按空格分割成单词列表，若长度与 pattern 不等直接返回 False。
2. 同步遍历：对每个位置 i，执行三次检查：
- 若
s[i]已在dic1中，检查其映射值是否等于pattern[i] - 若
pattern[i]已在dic2中，检查其映射值是否等于s[i] - 若均未出现，则建立双向映射
示例：pattern = "abba", s = "dog cat cat dog"
i=0: dic1={dog→a}, dic2={a→dog}
i=1: dic1={dog→a, cat→b}, dic2={a→dog, b→cat}
i=2: cat已在dic1中，映射为b，等于pattern[2]=b ✓
b已在dic2中，映射为cat，等于s[2]=cat ✓
i=3: dog已在dic1中，映射为a，等于pattern[3]=a ✓
a已在dic2中，映射为dog，等于s[3]=dog ✓
返回True3. 返回结果：遍历结束无冲突则返回 True。
复杂度分析
- 时间复杂度：O(n)，其中 n 为
pattern长度。需遍历一次所有字符，哈希表操作均为 O(1)。 - 空间复杂度：O(n)，需要两个哈希表存储最多 n 对映射关系。
参考代码
class Solution:
def wordPattern(self, pattern: str, s: str) -> bool:
s = s.split()
if len(pattern) != len(s):
return False
t = pattern
# 接下来的逻辑和 LC205. 同构字符串 一模一样
# 设置一个哈希集合用来存储字符串 s 当中的元素
dic1 = {}
# 设置一个哈希集合用来存储字符串 t 当中的元素
dic2 = {}
# 由于 t.length == s.length
# 按照顺序访问 s 和 t 中对应的元素
for i in range(len(pattern)):
# 1、访问的元素 s[i] 存在于 dic1 中
# 并且发现它对应的元素值和当前 t 中元素 t[i] 不相同
# 返回 False
if s[i] in dic1 and dic1[s[i]] != t[i]:
return False
# 2、访问的元素 t[i] 存在于 dic2 中
# 并且发现它对应的元素值和当前 s 中元素 s[i] 不相同
# 返回 False
if t[i] in dic2 and dic2[t[i]] != s[i]:
return False
# 3、访问的元素 s[i] 不存在于 dic1 中
# 存放到哈希集合中
if s[i] not in dic1:
# dic1[s[i]] = t[i]
dic1[s[i]] = t[i]
# 3、访问的元素 t[i] 不存在于 dic2 中
# 存放到哈希集合中
if t[i] not in dic2:
# dic2[t[i]] = s[i]
dic2[t[i]] = s[i]
# 返回 True
return True