[leetcode/lintcode 题解] 算法面试高频题详解：查找和替换模式

描述
你有一个单词列表 words 和一个模式 pattern，你想知道 words 中的哪些单词与模式匹配。
如果存在字母的排列 p ，使得将模式中的每个字母 x 替换为 p(x) 之后，我们就得到了所需的单词，那么单词与模式是匹配的。
（回想一下，字母的排列是从字母到字母的双射：每个字母映射到另一个字母，没有两个字母映射到同一个字母。）
返回 words 中与给定模式匹配的单词列表。
你可以按任何顺序返回答案。

1 =words.length =501 =pattern.length=words[i].length =20

在线评测地址：领扣题库官网

样例1
输入：words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb"
输出：["aqq","mee"]
"mee" 与模式匹配，因为存在排列 {a - m, b - e, ...}。
"ccc" 与模式不匹配，因为 {a - c, b - c, ...} 不是排列。
因为 a 和 b 映射到同一个字母。

样例2
输入: words = ["a","b","c"], pattern = "a"
输出: ["a","b","c"]
所有的字符串都匹配。

解题思路
遍历words，逐个匹配是否满足pattern，在匹配时，借助HashMap建立字符映射关系，条件是：每个字母映射到另一个字母中，没有两个字母映射到同一个字母。
源代码

public class Solution {
 * @param words: word list
 * @param pattern: pattern string
 * @return: list of matching words
 public List String findAndReplacePattern(String[] words, String pattern) {
 // Write your code here.
 int[] p = F(pattern);
 List String res = new ArrayList String 
 for (String w : words)
 if (Arrays.equals(F(w), p)) res.add(w);
 return res;
 public int[] F(String w) {
 HashMap Character, Integer m = new HashMap ();
 int n = w.length();
 int[] res = new int[n];
 for (int i = 0; i i++) {
 m.putIfAbsent(w.charAt(i), m.size());
 res[i] = m.get(w.charAt(i));
 return res;
}

更多题解参考：九章官网solution

本文转自网络，原文链接：https://developer.aliyun.com/article/784008
本站部分内容转载于网络，版权归原作者所有，转载之目的在于传播更多优秀技术内容，如有侵权请联系QQ/微信：153890879删除，谢谢！