0890. 查找和替换模式【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 双向映射

1. 📝 题目描述

• leetcode

你有一个单词列表 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 <= words.length <= 50
• 1 <= pattern.length = words[i].length <= 20

2. 🎯 s.1 - 双向映射

c

bool match(char* word, char* pattern) {
    int n = strlen(word);
    if (n != (int)strlen(pattern)) return false;
    char w2p[128] = {0}, p2w[128] = {0};
    for (int i = 0; i < n; i++) {
        char w = word[i], p = pattern[i];
        if (w2p[(int)w] && w2p[(int)w] != p) return false;
        if (p2w[(int)p] && p2w[(int)p] != w) return false;
        w2p[(int)w] = p; p2w[(int)p] = w;
    }
    return true;
}

char** findAndReplacePattern(char** words, int wordsSize, char* pattern, int* returnSize) {
    char** res = (char**)malloc(sizeof(char*) * wordsSize);
    *returnSize = 0;
    for (int i = 0; i < wordsSize; i++)
        if (match(words[i], pattern)) res[(*returnSize)++] = words[i];
    return res;
}

js

/**
 * @param {string[]} words
 * @param {string} pattern
 * @return {string[]}
 */
var findAndReplacePattern = function (words, pattern) {
  const match = (word) => {
    if (word.length !== pattern.length) return false
    const w2p = {},
      p2w = {}
    for (let i = 0; i < word.length; i++) {
      const w = word[i],
        p = pattern[i]
      if (w2p[w] && w2p[w] !== p) return false
      if (p2w[p] && p2w[p] !== w) return false
      w2p[w] = p
      p2w[p] = w
    }
    return true
  }
  return words.filter(match)
}

py

class Solution:
    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:
        def match(word: str) -> bool:
            w2p, p2w = {}, {}
            for w, p in zip(word, pattern):
                if w2p.setdefault(w, p) != p: return False
                if p2w.setdefault(p, w) != w: return False
            return True
        return [w for w in words if match(w)]

• 时间复杂度：$O(n\times m)$，其中 n 是单词数，m 是单词长度
• 空间复杂度：$O(m)$

算法思路：

• 对每个单词建立与模式的双向映射（word→pattern 和 pattern→word）
• 若映射冲突则不匹配