查找和替换模式 图解题解

这道题到底在问什么

输入

words=["abc","mee","aqq","ccc"], pattern="abb"

输出

["mee","aqq"]

输入

为什么 "ccc" 不行

输出

pattern 的 a 和 b 都得映射成 c，两个字母撞到同一个，不是双射

最优解：一步一步想明白

1. 3记住这套「一位一查、双向一致才放行」，下面每一帧都在套它。
2. 4先看清模式 "abb"：它的形状是「第一位单独，后两位相同」。任何匹配它的词，也必须是这个形状。逐个单词检验。
3. 5换到单词 "abc"。两张映射表清空，准备一位一位地和模式 "abb" 对。
4. 6第 0 位是新字母对:把「词 a → 式 a」记进 f，反过来「式 a → 词 a」记进 g。这一位绿了。
5. 7第 1 位是新字母对:把「词 b → 式 b」记进 f，反过来「式 b → 词 b」记进 g。这一位绿了。
6. 8第 2 位想把词 "c" 和式 "b" 配起来，可映射表里 式字母 "b" 早先已被词字母 "b" 占用，这一位却要它对应 "c"。撞车了，这个词出局。
7. 9"abc" 在第 2 位就撞了车，没法构成双射。丢弃，不进答案。
8. 10换到单词 "mee"。两张映射表清空，准备一位一位地和模式 "abb" 对。
9. 11第 0 位是新字母对:把「词 m → 式 a」记进 f，反过来「式 a → 词 m」记进 g。这一位绿了。
10. 12第 1 位是新字母对:把「词 e → 式 b」记进 f，反过来「式 b → 词 e」记进 g。这一位绿了。
11. 13第 2 位的词 "e" 和式 "b" 在两张表里都已登记且正好对得上，一致通过，绿色推进到第 2 位。
12. 14"mee" 从头到尾两张表都没冲突，说明能用一个双射把模式变成它。收进答案。
13. 15换到单词 "aqq"。两张映射表清空，准备一位一位地和模式 "abb" 对。
14. 16第 0 位是新字母对:把「词 a → 式 a」记进 f，反过来「式 a → 词 a」记进 g。这一位绿了。
15. 17第 1 位是新字母对:把「词 q → 式 b」记进 f，反过来「式 b → 词 q」记进 g。这一位绿了。
16. 18第 2 位的词 "q" 和式 "b" 在两张表里都已登记且正好对得上，一致通过，绿色推进到第 2 位。
17. 19"aqq" 从头到尾两张表都没冲突，说明能用一个双射把模式变成它。收进答案。
18. 20换到单词 "ccc"。两张映射表清空，准备一位一位地和模式 "abb" 对。
19. 21第 0 位是新字母对:把「词 c → 式 a」记进 f，反过来「式 a → 词 c」记进 g。这一位绿了。
20. 22第 1 位想把词 "c" 和式 "b" 配起来，可映射表里 词字母 "c" 早先已对应式字母 "a"，这一位却要它对应 "b"。撞车了，这个词出局。
21. 23"ccc" 在第 1 位就撞了车，没法构成双射。丢弃，不进答案。
22. 24四个单词都对完了,能匹配模式 "abb" 的是 "mee" 和 "aqq"。这就是最终答案。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

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)]

#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;
    }
};

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;
    }
}

复杂度

面试官可能追问