LeetCode 题解工作台
查找和替换模式
你有一个单词列表 words 和一个模式 pattern ，你想知道 words 中的哪些单词与模式匹配。 如果存在字母的排列 p ，使得将模式中的每个字母 x 替换为 p(x) 之后，我们就得到了所需的单词，那么单词与模式是匹配的。 （回想一下，字母的排列是从字母到字母的双射：每个字母映射到另一个…
3
题型
6
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
class Solution: def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
你有一个单词列表 words 和一个模式 pattern，你想知道 words 中的哪些单词与模式匹配。
如果存在字母的排列 p ，使得将模式中的每个字母 x 替换为 p(x) 之后，我们就得到了所需的单词，那么单词与模式是匹配的。
（回想一下，字母的排列是从字母到字母的双射：每个字母映射到另一个字母，没有两个字母映射到同一个字母。）
返回 words 中与给定模式匹配的单词列表。
你可以按任何顺序返回答案。
示例：
输入：words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb"
输出：["mee","aqq"]
解释：
"mee" 与模式匹配，因为存在排列 {a -> m, b -> e, ...}。
"ccc" 与模式不匹配，因为 {a -> c, b -> c, ...} 不是排列。
因为 a 和 b 映射到同一个字母。
提示：
1 <= pattern.length <= 201 <= words.length <= 50words[i].length == pattern.lengthpattern和words[i]只包含小写英文字母。
解题思路
方法一：哈希表
class Solution:
def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:
def match(s, t):
m1, m2 = [0] * 128, [0] * 128
for i, (a, b) in enumerate(zip(s, t), 1):
if m1[ord(a)] != m2[ord(b)]:
return False
m1[ord(a)] = m2[ord(b)] = i
return True
return [word for word in words if match(word, pattern)]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n * m) where n is the number of words and m is the length of the pattern, since each word is scanned once. Space complexity is O(m) for the hash tables storing character mappings for each word. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Check if candidates are creating both forward and reverse mappings correctly.
- question_mark
Watch for confusion between bijective and non-bijective letter replacement.
- question_mark
Notice if array scanning is done without efficient hash lookups.
常见陷阱
外企场景- error
Mapping two different pattern letters to the same word letter, violating bijection.
- error
Forgetting to check the inverse mapping from word letters back to pattern letters.
- error
Assuming words of different lengths than pattern can match without validation.
进阶变体
外企场景- arrow_right_alt
Find words that match a pattern ignoring repeated letters, relaxing bijection constraint.
- arrow_right_alt
Return the indices of words matching the pattern instead of the words themselves.
- arrow_right_alt
Apply the pattern matching on uppercase letters or mixed-case strings.