问题描述

给定一个模式字符串 pattern 和一个普通字符串 s，判断字符串 s 是否遵循相同的规律。这里的"遵循"指pattern中的每个字符和字符串s中的每个非空单词之间存在着双向的一一对应关系。

题目解析

• 核心考点：哈希映射（Hash Map）的应用
• 重点：需要确保双向的一一对应关系
• 考察内容：字符串处理、数据结构应用、映射关系处理
• 难点：需要同时保证 pattern 到 word 和 word 到 pattern 的唯一映射

解决方案

使用两个哈希表分别存储：

1. pattern中字符到单词的映射
2. 单词到pattern中字符的映射
   通过维护这两个映射来确保双向的一一对应关系。

算法步骤

1. 将字符串s按空格分割成单词列表
2. 检查pattern的长度和单词数量是否相等，不相等则返回False
3. 创建两个字典，分别存储字符到单词和单词到字符的映射
4. 同时遍历pattern和单词列表：
   • 检查当前字符是否已经映射到其他单词
   • 检查当前单词是否已经映射到其他字符
   • 如果都没有映射，建立双向映射
   • 如果已有映射，验证是否匹配
5. 如果全部匹配成功，返回True

关键点说明

1. 需要使用两个哈希表来保证双向的一一对应
2. 字符串分割后需要检查长度匹配
3. 在遍历过程中及时检查和维护映射关系
4. 注意处理边界情况

代码实现

def wordPattern(pattern: str, s: str) -> bool:
    # 将字符串分割成单词列表
    words = s.split()
    
    # 检查长度是否匹配
    if len(pattern) != len(words):
        return False
    
    # 创建两个字典存储映射关系
    char_to_word = {}    # 字符到单词的映射
    word_to_char = {}    # 单词到字符的映射
    
    # 同时遍历pattern和words
    for char, word in zip(pattern, words):
        # 检查字符到单词的映射
        if char in char_to_word:
            if char_to_word[char] != word:
                return False
        else:
            char_to_word[char] = word
            
        # 检查单词到字符的映射
        if word in word_to_char:
            if word_to_char[word] != char:
                return False
        else:
            word_to_char[word] = char
    
    return True

图文解释

以示例 pattern = "abba", s = "dog cat cat dog" 为例：

1. 首先分割字符串：

   • pattern = ['a', 'b', 'b', 'a']
   • words = ['dog', 'cat', 'cat', 'dog']

2. 建立映射关系：

   • 第一步：'a' -> 'dog' 和 'dog' -> 'a'
   • 第二步：'b' -> 'cat' 和 'cat' -> 'b'
   • 第三步：检查 'b' -> 'cat' （已存在且匹配）
   • 第四步：检查 'a' -> 'dog' （已存在且匹配）

最终的映射关系：

• char_to_word = {'a': 'dog', 'b': 'cat'}
• word_to_char = {'dog': 'a', 'cat': 'b'}

算法分析

• 时间复杂度：O(n)，其中 n 是 pattern 的长度
  • 字符串分割需要 O(n)
  • 遍历和哈希表操作都是 O(1)
• 空间复杂度：O(n)
  • 需要两个哈希表存储映射关系
  • 存储分割后的单词列表

结论

这是一道考察哈希表应用的经典题目，关键在于：

1. 理解双向一一对应的概念
2. 正确使用哈希表存储和验证映射关系
3. 注意处理边界条件和异常情况

解决这类问题的通用思路是：

1. 使用合适的数据结构存储映射关系
2. 确保映射的唯一性
3. 通过遍历同时维护和验证映射关系