查找和替换模式 图解题解

哪些单词换套字母表就能拼成 pattern

给一串单词 words 和模式串 pattern，挑出所有能匹配 pattern 的单词。匹配叫双射：存在一套字母替换，不同字母换成不同字母、不撞到一起，把 pattern 替换后正好得到那个单词。题面例子 words=["abc","mee","aqq","ccc"]、pattern="abb"，答案是 ["mee","aqq"]。abb 的形状是「头一位单、后两位相同」，只有 mee、aqq 对得上。

只记「词→式」一张表，为什么会放错人

先试只开一张映射表：逐位记「词字母 → 式字母」，同一个词字母始终指向同一个式字母就算过。这只拦得住『一个词字母对应两个式字母』一种冲突。abc 对 abb 时，词 a→式 a、b→式 b、c→式 b，三个词字母互不相同，表里全程没矛盾，abc 就被误放行。可 abc 的 b、c 明明不同，单向表却看不出「b、c 挤到了同一个式字母 b」。

补一张反向表，双向一致才配叫双射

补第二张表，反过来记「式字母 → 词字母」。逐位查时两张表都问：词字母、式字母只要之前登记过，就都得仍指向原先配对的那个。回到 abc 第三位，词 c 在正向表是新面孔，但反向表里式 b 早被词 b 占住、又要它对应 c，反向表当场拦下。

两表各管一个方向，缺一不可：正向表挡『一个词字母想对两个式字母』，ccc 栽在这（词 c 先配 a 又想配 b）；反向表挡『两个词字母挤向同一个式字母』，abc 栽的正是这类。只守一边，总有一类撞车溜过去。

一位一位地查，一撞车就立刻收手

每个单词都从两张空表起步，和 pattern 逐位往下走。每到一位两张表各验一遍：对得上就把「词字母 ↔ 式字母」双向登记，再看下一位；任一张表冲突就立刻出局，后面不再看，前面矛盾了后面再对也救不回。走完两表始终一致就收进答案。

拿 abc、mee、aqq、ccc 逐位对 abb

abc 对 abb：第 0 位 a 配 a、第 1 位 b 配 b 都是新对，双向记下；第 2 位 c 要配 b，反向表里式 b 已归词 b，撞车出局。mee 对 abb：m 配 a、e 配 b 是新对，第 2 位又 e 配 b，两表都已登记且吻合，三位过，进答案。

aqq 也顺：q 配 b 后第 2 位又一次 q 配 b 正好对上，收进答案。ccc 卡在第 1 位：第 0 位 c 配 a，第 1 位 c 又要配 b，正向表里 c 已指向 a，冲突出局。能匹配 abb 的是 mee、aqq，正是题面给的 ["mee","aqq"]。

扫一遍要多久，单字母和全同字符怎么算

设有 n 个单词、每个长 L，逐位扫一遍两张定长小表，总时间 O(n·L)；映射只落在 26 个小写字母上，两张表大小固定，空间 O(1)。pattern 若只有一个字母，任何等长单词都天然匹配；单词形状和 pattern 对不上则一个都进不了答案，比如 abb 要后两位相同、abc 不同当场排除。

参考代码没真开两张字典，而是给每个字母记下最近出现的位置，逐位要求词字母与式字母的最近位置相等，相等即说明它俩一路成对现身，和两张映射表等价。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
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)]

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    vector<string> findAndReplacePattern(vector<string>& words, string pattern) {
        vector<string> ans;
        auto match = [](string& s, string& t) {
            int m1[128] = {0};
            int m2[128] = {0};
            for (int i = 0; i < s.size(); ++i) {
                if (m1[s[i]] != m2[t[i]]) return 0;
                m1[s[i]] = i + 1;
                m2[t[i]] = i + 1;
            }
            return 1;
        };
        for (auto& word : words)
            if (match(word, pattern)) ans.emplace_back(word);
        return ans;
    }
};

Java

import java.util.*;
class Solution {
    public List<String> findAndReplacePattern(String[] words, String pattern) {
        List<String> ans = new ArrayList<>();
        for (String word : words) {
            if (match(word, pattern)) {
                ans.add(word);
            }
        }
        return ans;
    }

    private boolean match(String s, String t) {
        int[] m1 = new int[128];
        int[] m2 = new int[128];
        for (int i = 0; i < s.length(); ++i) {
            char c1 = s.charAt(i);
            char c2 = t.charAt(i);
            if (m1[c1] != m2[c2]) {
                return false;
            }
            m1[c1] = i + 1;
            m2[c2] = i + 1;
        }
        return true;
    }
}