查找和替换模式

题目描述

你有一个单词列表 words 和一个模式字符串 pattern。需要找出 words 中所有满足以下条件的单词：单词与模式字符串 pattern 之间存在双向的、一一映射关系。

具体来说，对于单词 word 和模式 pattern：

• 每个字母的映射必须是一对一的：
  • pattern 中的每个字母必须映射到 word 中同一个字母（不能映射到两个不同的字母）。
  • word 中的每个字母也必须映射回 pattern 中同一个字母（不能映射到两个不同的字母）。

换句话说，word 和 pattern 必须是同构字符串（双向同构）。

示例：

• 输入：words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb"
  输出：["mee","aqq"]
  解释：
  • "mee"：模式 "abb" 中 a→m, b→e，且 e 只映射回 b，满足条件。
  • "aqq"：模式 "abb" 中 a→a, b→q，且 q 只映射回 b，满足条件。
  • 其他单词不满足，例如 "abc" 中 a→a, b→b, c→c，模式 "abb" 要求第二个和第三个字母相同，但 "b" 和 "c" 不同，不符合。
  • "ccc" 中所有字母相同，但模式 "abb" 中第一个字母 a 和第二个字母 b 不同，因此 "c" 不能同时映射到 a 和 b，不符合。

解题思路

我们需要检查每个单词是否与模式字符串构成双向同构。这可以通过两个哈希映射来实现：

1. 模式到单词的映射（p_to_w）：记录 pattern 中每个字符映射到 word 中的对应字符。
2. 单词到模式的映射（w_to_p）：记录 word 中每个字符映射到 pattern 中的对应字符。

遍历单词和模式的每个位置，同时检查两个映射是否一致：

• 如果 p_to_w[pattern[i]] 已存在且不等于 word[i]，说明模式中的同一个字母映射到了单词中的不同字母，不符合。
• 如果 w_to_p[word[i]] 已存在且不等于 pattern[i]，说明单词中的同一个字母映射到了模式中的不同字母，不符合。
• 否则，建立双向映射，继续检查。

循序渐进讲解

步骤 1：理解双向映射

例如 pattern = "abb", word = "mee"：

• 位置 0: pattern[0]='a' 映射到 word[0]='m'，同时 word[0]='m' 映射到 pattern[0]='a'。
• 位置 1: pattern[1]='b' 映射到 word[1]='e'，同时 word[1]='e' 映射到 pattern[1]='b'。
• 位置 2: pattern[2]='b' 映射到 word[2]='e'，检查 p_to_w['b'] 已经是 'e'，一致；同时 word[2]='e' 映射到 pattern[2]='b'，检查 w_to_p['e'] 已经是 'b'，一致。
  因此满足条件。

步骤 2：设计检查函数

我们可以写一个函数 isMatch(word, pattern)，用两个哈希表（字典）记录映射关系。

伪代码：

function isMatch(word, pattern):
    if len(word) != len(pattern):
        return false
    初始化 p_to_w 为空字典
    初始化 w_to_p 为空字典
    for i 从 0 到 len(word)-1:
        pc = pattern[i]
        wc = word[i]
        if pc 在 p_to_w 中 且 p_to_w[pc] != wc:
            return false
        if wc 在 w_to_p 中 且 w_to_p[wc] != pc:
            return false
        设置 p_to_w[pc] = wc
        设置 w_to_p[wc] = pc
    return true

步骤 3：处理单词列表

遍历 words 中的每个单词，调用 isMatch，将匹配的单词加入结果列表。

步骤 4：复杂度分析

• 设 n 为单词个数，L 为单词和模式的长度（假设长度相同，否则直接不匹配）。
• 每个单词检查一次，每次检查需要 O(L) 时间，使用两个哈希表，空间 O(L)。
• 总时间复杂度 O(n * L)，空间复杂度 O(L)（用于检查的临时哈希表）。

示例推导

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

1. word = "abc", pattern = "abb"

   • i=0: p_to_w['a']='a', w_to_p['a']='a'
   • i=1: p_to_w['b']='b', w_to_p['b']='b'
   • i=2: pattern[2]='b', p_to_w['b'] 已存在且为 'b'，但 word[2]='c'，'b' != 'c' → 不匹配。

2. word = "mee", pattern = "abb"

   • i=0: p_to_w['a']='m', w_to_p['m']='a'
   • i=1: p_to_w['b']='e', w_to_p['e']='b'
   • i=2: pattern[2]='b', p_to_w['b']='e' 等于 word[2]='e'；w_to_p['e']='b' 等于 pattern[2]='b' → 匹配。

3. word = "ccc", pattern = "abb"

   • i=0: p_to_w['a']='c', w_to_p['c']='a'
   • i=1: pattern[1]='b', p_to_w['b']='c'，但 word[1]='c' 对应 w_to_p['c'] 已经是 'a'，而 pattern[1]='b'，'a' != 'b' → 不匹配。

最终匹配的单词是 ["mee","aqq"]。

代码实现（Python示例）

def findAndReplacePattern(words, pattern):
    def is_match(word, pattern):
        if len(word) != len(pattern):
            return False
        p_to_w = {}
        w_to_p = {}
        for pc, wc in zip(pattern, word):
            if pc in p_to_w and p_to_w[pc] != wc:
                return False
            if wc in w_to_p and w_to_p[wc] != pc:
                return False
            p_to_w[pc] = wc
            w_to_p[wc] = pc
        return True
    
    return [w for w in words if is_match(w, pattern)]

# 测试
words = ["abc","deq","mee","aqq","dkd","ccc"]
pattern = "abb"
print(findAndReplacePattern(words, pattern))  # 输出: ["mee", "aqq"]

关键点总结

1. 双向映射：必须同时维护两个哈希表，确保一一对应。
2. 长度检查：如果单词长度与模式不同，直接不匹配。
3. 实时检查：在遍历过程中一旦发现冲突就立即返回 False，提高效率。
4. 适用范围：该方法适用于任何字符集（字母、数字等），因为哈希表可以处理任意字符。

这个题目是哈希表在字符串模式匹配中的典型应用，通过双向映射确保了一一对应的同构关系。