LeetCode 290. Word Pattern 题解

LeetCode 290. Word Pattern 题解题目描述给定一种规律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解题思路方法哈希表思路使用两个哈希表一个用于存储字符到单词的映射另一个用于存储单词到字符的映射将字符串s分割成单词列表检查pattern的长度和单词列表的长度是否相等如果不相等返回false遍历pattern和单词列表对于每个字符和单词如果字符在第一个哈希表中存在但对应的单词与当前单词不同返回false如果单词在第二个哈希表中存在但对应的字符与当前字符不同返回false如果两者都不存在将字符和单词互相映射遍历结束后返回true复杂度分析时间复杂度O(n)其中 n 是pattern的长度或单词列表的长度。只需要遍历一次。空间复杂度O(n)需要使用哈希表来存储映射关系。代码实现方法哈希表class Solution: def wordPattern(self, pattern: str, s: str) - bool: # 将字符串 s 分割成单词列表 words s.split() # 检查 pattern 的长度和单词列表的长度是否相等 if len(pattern) ! len(words): return False # 使用两个哈希表分别存储字符到单词的映射和单词到字符的映射 char_to_word {} word_to_char {} # 遍历 pattern 和单词列表 for char, word in zip(pattern, words): # 检查字符到单词的映射 if char in char_to_word: if char_to_word[char] ! word: return False # 检查单词到字符的映射 if word in word_to_char: if word_to_char[word] ! char: return False # 如果两者都不存在建立映射 if char not in char_to_word and word not in word_to_char: char_to_word[char] word word_to_char[word] char # 遍历结束后返回 true return True测试用例测试用例 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总结本题是哈希表的经典应用问题主要考察对哈希表思想的理解和使用。通过使用两个哈希表我们可以高效地判断字符串s是否遵循给定的规律pattern。哈希表的核心思想是使用两个哈希表来存储字符到单词的映射和单词到字符的映射确保每个字符对应唯一的单词每个单词对应唯一的字符。这种方法不仅适用于单词规律问题还可以应用于许多其他需要建立双向映射的问题。掌握哈希表的使用对于解决这类问题非常重要。