0890. Find and Replace Pattern¶
题目信息¶
- 题号:
0890
- 难度:
Medium
- 主题:
字符串、模式匹配、双射映射
- 原题:
- 重点:
模式字符与单词字符之间必须建立一一对应关系;相同模式字符映射相同字母,不同模式字符不能映射到同一字母
题目重述¶
给定字符串数组 words 和模式字符串 pattern,每个单词都与模式等长。若能为 pattern 中出现的每种字符指定一个小写字母,使替换模式中的全部字符后恰好得到某个单词,并且不同模式字符必须指定不同字母,则该单词与模式匹配。
这种对应关系必须是双射:同一个模式字符在所有位置都映射到同一个单词字符,两个不同模式字符不能映射到同一字符。请返回 words 中所有匹配的单词,结果顺序不限。
1 <= words.length <= 50,1 <= pattern.length == words[i].length <= 20,所有字符串只包含小写英文字母。
自建示例¶
相同重复结构可以使用不同字母:
输入:words = ["xyy","yxx","xyz","zzz"], pattern = "abb"
输出:["xyy","yxx"]
解释:前两个单词都满足首字符不同于后两个相同字符;xyz 的后三个位置结构不匹配,zzz 会让模式中的 a 和 b 映射到同一字母。返回顺序可以不同。
模式字符全部不同:
输入:words = ["mno","mom"], pattern = "abc"
输出:["mno"]
解释:pattern 的三个字符互不相同,所以匹配单词的三个位置也必须使用不同字母。mno 满足该条件;mom 的首尾相同,会让 a 与 c 映射到同一字母,因此不匹配。