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

题目描述
你有一个单词列表 words 和一个模式字符串 pattern，需要找出 words 中所有与 pattern 匹配的单词。
匹配的定义是：单词中的每个字母与模式中的每个字母必须存在双向唯一映射。
例如：

• pattern = "abb"，单词 "cdd" 匹配（a→c，b→d），但 "ccc" 不匹配（a→c，但 b 也试图映射到 c，违反唯一性）。
• pattern = "abc"，单词 "xyz" 匹配（a→x，b→y，c→z），但 "xzx" 不匹配（a→x，b→z，但 c 试图映射到 x，而 x 已被 a 占用）。

解题过程

步骤1：理解匹配规则
匹配需要满足两个条件：

1. 单向映射唯一性：pattern 中的每个字符映射到单词中的对应字符必须唯一（即 pattern 的同一字符不能映射到单词的不同字符）。
2. 双向映射唯一性：单词中的每个字符映射回 pattern 也必须唯一（即单词的不同字符不能映射到 pattern 的同一字符）。
   这等价于要求两个字符串之间的映射是双射（一一对应）。

步骤2：设计映射检查方法
我们可以用两个哈希表分别记录：

• p_to_w：pattern 中字符到单词中字符的映射。
• w_to_p：单词中字符到 pattern 中字符的映射。
  遍历每个位置 i：
• 如果 p_to_w 中已存在 pattern[i] 的映射，但映射值不等于 word[i]，则匹配失败。
• 如果 w_to_p 中已存在 word[i] 的映射，但映射值不等于 pattern[i]，则匹配失败。
• 否则，建立双向映射。

步骤3：实现匹配函数
对每个单词执行以下检查：

def match(word, pattern):
    if len(word) != len(pattern):
        return False
    p_to_w = {}  # pattern字符 -> word字符
    w_to_p = {}  # word字符 -> pattern字符
    for p_char, w_char in zip(pattern, word):
        if p_char in p_to_w:
            if p_to_w[p_char] != w_char:
                return False
        else:
            p_to_w[p_char] = w_char
        if w_char in w_to_p:
            if w_to_p[w_char] != p_char:
                return False
        else:
            w_to_p[w_char] = p_char
    return True

步骤4：遍历单词列表
对 words 中的每个单词调用 match 函数，收集所有匹配的单词。

举例验证
以 words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb" 为例：

• "abc"：a→a，b→b，但 b 映射到 c 时，p_to_w 中 b 已映射到 b，冲突 → 不匹配。
• "mee"：m→a，e→b，e→b（一致）→ 匹配。
• "aqq"：a→a，q→b，q→b（一致）→ 匹配。
• "ccc"：c→a，c→b（冲突：p_to_w 中 c 已映射到 a，但当前需要映射到 b）→ 不匹配。
  结果：["mee","aqq"]。

总结
本题通过双向哈希表确保映射的唯一性，是哈希表维护双射关系的典型应用。时间复杂度为 O(n * k)，其中 n 是单词数量，k 是单词长度。