哈希算法题目：查找和替换模式

题目描述

你有一个单词列表 words 和一个模式字符串 pattern。你需要从单词列表中找到所有与模式匹配的单词，并将这些单词以列表形式返回。

“匹配”定义如下：
一个单词与一个模式匹配，当且仅当存在一个字母之间的双射（即一个一一对应的映射关系），使得将单词中的每个字母替换为模式中对应的字母后，可以得到该模式。反之亦然。这意味着匹配是双向的、一一对应的。

简单来说：我们可以为单词和模式分别建立一个“编码规则”。如果两个字符串能用同一套编码规则（从字符到第一个出现位置的索引，或者到另一个唯一标识）进行转换，并且转换后的结果序列完全相同，那么它们就互相匹配。

示例 1：
输入：words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb"
输出：["mee","aqq"]
解释：

• "mee" 与模式 "abb" 匹配，因为从 m->a, e->b 的映射是有效的，并且满足一一对应（"mee"编码后是"abb"）。
• "aqq" 与 "abb" 匹配，因为 a->a, q->b 的映射是有效的。
• "abc" 不匹配，因为 "abc" 编码后是"abc"，不是"abb"。
• "deq" 编码后是"abc"。
• "dkd" 编码后是"aba"。
• "ccc" 编码后是"aaa"。

示例 2：
输入：words = ["a","b","c"], pattern = "a"
输出：["a","b","c"]
解释：模式只有一个字母，任何只有一个字母的单词都与之匹配，因为单字母的映射总是双向唯一的。

解题思路

核心问题是判断两个字符串（单词和模式）的“结构”是否完全相同。这里“结构”指的是字符之间的对应关系模式。

我们可以为任何一个字符串创建一个“规范化”的编码，使得所有结构相同的字符串都被编码成同一个序列。常用的方法有两种：

1. 基于首次出现位置的编码：遍历字符串，将每个字符映射为它在该字符串中第一次出现的索引。如果字符重复出现，就沿用第一次的索引。
2. 基于字符到字符的映射关系：建立从单词到模式的映射，同时也建立从模式到单词的映射，确保是双射（一一对应）。

我们将详细讲解第二种方法，因为它更直观地体现了“双射”的概念。

循序渐进讲解

步骤 1: 理解“双射”

对于单词 word 和模式 pattern 要匹配，必须满足：

• word 中的每个字符唯一地映射到 pattern 中的一个字符。
• pattern 中的每个字符也唯一地映射到 word 中的一个字符。
  这意味着，我们不能有 word 中两个不同字符映射到 pattern 的同一个字符，也不能有 pattern 中两个不同字符映射到 word 的同一个字符。

例如：

• word = "mee", pattern = "abb"。

  • 映射 m -> a, e -> b 是合理的。
  • 检查双向性：
    • 正向：m 只映射到 a，e 只映射到 b。（满足）
    • 反向：a 只被 m 映射，b 只被 e 映射。（满足）
  • 所以匹配。

• word = "ccc", pattern = "abb"。

  • 尝试建立映射：c -> a (对于第一个c)，c -> b (对于第二个c)，c -> b (对于第三个c)。
  • 这里正向映射就失败了，因为 word 中的同一个字符 c 试图映射到 pattern 中的两个不同字符 a 和 b。这违反了“一一对应”中的“单射”要求（一个原像只能有一个像）。所以不匹配。

步骤 2: 设计算法

我们需要遍历 words 列表中的每个 word，并检查它是否与给定的 pattern 匹配。

对于单个 word 和 pattern 的匹配检查，我们可以这样做：

1. 如果 word 的长度不等于 pattern 的长度，直接返回不匹配。
2. 初始化两个哈希表（字典）：
   • map_w_to_p: 用于记录从 word 的字符到 pattern 字符的映射。
   • map_p_to_w: 用于记录从 pattern 的字符到 word 字符的映射。
3. 同时遍历 word 和 pattern 的每一个对应位置的字符（w_char 和 p_char）：
   a. 检查正向映射：如果 w_char 已经在 map_w_to_p 中，但它的映射值不等于当前的 p_char，则说明 w_char 想要映射到另一个 p_char，破坏了唯一性，返回不匹配。
   b. 检查反向映射：如果 p_char 已经在 map_p_to_w 中，但它的映射值不等于当前的 w_char，则说明 p_char 想要被另一个 w_char 映射，破坏了唯一性，返回不匹配。
   c. 如果上述检查都通过，则将当前的映射关系存入两个哈希表：map_w_to_p[w_char] = p_char 和 map_p_to_w[p_char] = w_char。
4. 如果成功遍历完所有字符，说明所有映射关系都是一一对应的，返回匹配。

步骤 3: 具体例子演算

以 word = "aqq", pattern = "abb" 为例：

1. 长度都是3，继续。
2. 初始化两个空字典。
3. 开始遍历：
   • i=0: w_char='a', p_char='a'。
     • map_w_to_p 中没有 'a'，map_p_to_w 中没有 'a'。
     • 存入：map_w_to_p['a'] = 'a', map_p_to_w['a'] = 'a'。
   • i=1: w_char='q', p_char='b'。
     • map_w_to_p 中没有 'q'，map_p_to_w 中没有 'b'。
     • 存入：map_w_to_p['q'] = 'b', map_p_to_w['b'] = 'q'。
   • i=2: w_char='q', p_char='b'。
     • 检查正向：map_w_to_p 中有 'q'，其值为 'b'，等于当前 p_char='b'，通过。
     • 检查反向：map_p_to_w 中有 'b'，其值为 'q'，等于当前 w_char='q'，通过。
4. 遍历结束，返回匹配。

以 word = "ccc", pattern = "abb" 为例：

1. 长度都是3，继续。
2. 初始化两个空字典。
3. 开始遍历：
   • i=0: w_char='c', p_char='a'。
     • 存入：map_w_to_p['c'] = 'a', map_p_to_w['a'] = 'c'。
   • i=1: w_char='c', p_char='b'。
     • 检查正向：map_w_to_p 中有 'c'，其值为 'a'，不等于当前 p_char='b'。冲突！ 返回不匹配。

步骤 4: 复杂度分析

• 时间复杂度：O(N * M)，其中 N 是 words 列表的长度，M 是 pattern 的长度（也是每个需要检查的 word 的长度）。因为我们对于 N 个单词，每个都进行了一次 O(M) 的遍历检查。
• 空间复杂度：O(M)。在每次检查单个单词时，我们使用了两个哈希表，在最坏情况下（所有字符都不同），它们会存储 M 个键值对，因此是 O(M) 的空间。由于检查是顺序进行的，空间可以复用。

步骤 5: 代码实现（Python示例）

def findAndReplacePattern(words, pattern):
    def matches(word, pattern):
        # 长度不同，直接不匹配
        if len(word) != len(pattern):
            return False
        
        map_w_to_p = {} # 单词字符 -> 模式字符
        map_p_to_w = {} # 模式字符 -> 单词字符
        
        for w_char, p_char in zip(word, pattern):
            # 检查正向映射冲突
            if w_char in map_w_to_p and map_w_to_p[w_char] != p_char:
                return False
            # 检查反向映射冲突
            if p_char in map_p_to_w and map_p_to_w[p_char] != w_char:
                return False
            # 建立新的映射关系
            map_w_to_p[w_char] = p_char
            map_p_to_w[p_char] = w_char
        
        return True
    
    result = []
    for word in words:
        if matches(word, pattern):
            result.append(word)
    return result

# 测试用例
print(findAndReplacePattern(["abc","deq","mee","aqq","dkd","ccc"], "abb"))
# 输出: ['mee', 'aqq']
print(findAndReplacePattern(["a","b","c"], "a"))
# 输出: ['a', 'b', 'c']

总结

这道题的关键在于理解并实现“字符串结构等价”的检查，核心是维护一个双向的、一一对应的字符映射关系。我们通过使用两个哈希表，在遍历过程中同时检查和维护从单词到模式、从模式到单词的映射，确保了匹配的双射性质。这个方法清晰、高效，是解决此类“模式匹配”问题的经典哈希应用。