| [890. 查找和替换模式](https://leetcode.cn/problems/find-and-replace-pattern/) | [LeetCode 题解链接](https://leetcode.cn/problems/find-and-replace-pattern/solution/by-ac_oier-s4cw/) | 中等 | 🤩🤩🤩🤩 |

| [890. 查找和替换模式](https://leetcode.cn/problems/find-and-replace-pattern/) | [LeetCode 题解链接](https://leetcode.cn/problems/find-and-replace-pattern/solution/by-ac_oier-s4cw/) | 中等 | 🤩🤩🤩🤩 |

这是 LeetCode 上的 **[890. 查找和替换模式](https://leetcode.cn/problems/find-and-replace-pattern/solution/by-ac_oier-s4cw/)** ，难度为 **中等**。

Tag : 「哈希表」、「模拟」

你有一个单词列表 `words` 和一个模式  `pattern`，你想知道 `words` 中的哪些单词与模式匹配。

如果存在字母的排列 `p` ，使得将模式中的每个字母 `x` 替换为 `p(x)` 之后，我们就得到了所需的单词，那么单词与模式是匹配的。

（回想一下，字母的排列是从字母到字母的双射：每个字母映射到另一个字母，没有两个字母映射到同一个字母。）

返回 `words` 中与给定模式匹配的单词列表。

你可以按任何顺序返回答案。

示例：

提示：

* $1 <= words.length <= 50$

* $1 <= pattern.length = words[i].length <= 20$

根据题意进行模拟即可，使用 `map` 记录具体的映射关系，使用 `vis` 记录哪些字符已被映射，利用字符集大小只有 $26$，我们可以使用数组充当哈希表。

代码：

class Solution {

public List<String> findAndReplacePattern(String[] ws, String pe) {

List<String> ans = new ArrayList<>();

int[] map = new int[26], vis = new int[26];

for (String s : ws) {

Arrays.fill(map, -1);

Arrays.fill(vis, 0);

boolean ok = true;

for (int i = 0; i < pe.length() && ok; i++) {

int c1 = s.charAt(i) - 'a', c2 = pe.charAt(i) - 'a';

if (map[c1] == -1 && vis[c2] == 0) {

map[c1] = c2; vis[c2] = 1;

} else if (map[c1] != c2) ok = false;

}

if (ok) ans.add(s);

}

return ans;

}

}

* 时间复杂度：$O(\sum_{i = 0}^{n}len(ws[i]) + n \times C)$，其中 $C = 26$ 代表字符集大小

* 空间复杂度：$O(C)$

这是我们「刷穿 LeetCode」系列文章的第 `No.890` 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。