一、题目描述

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

二、输入输出描述

　　1、示例：

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

　　2、提示：

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

三、思路

四、代码

　　根据上面的思路，使用map实现

1 package cn.zifuchuan; 2  3 import java.util.ArrayList; 4 import java.util.HashMap; 5 import java.util.List; 6 import java.util.Map; 7  8 public class Test1 { 9 10     /*11      * words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abc"12      */13     public static void main(String[] args) {14          String[] words = {"abcc","deqq","meee","aqq","dkd","ccc"};15          String pattern = "abcc";16          System.out.println(findAndReplacePattern(words, pattern));17          18     }19     20     /**21      * @param words 输入的字符串22      * @param pattern 找到符合这个形式的字符串23      * @return24      */25     public static List
     
       findAndReplacePattern(String[] words, String pattern) {26         List
      
        res = new ArrayList<>();27         Map
       
         map = new HashMap<>();28         for (String word : words) {29             //先简单的判断长度30             if (word.length() != pattern.length())31                 continue;32             boolean flag = true; //判断当前是不是和pattern形式一样的字符串33             for (int i = 0; i < word.length(); i++) {34                 /*35                  * containsKey36                  * boolean containsKey(Object key)如果此映射包含指定键的映射关系，则返回 true。37                  * 更确切地讲，当且仅当此映射包含针对满足 (key==null ? k==null : key.equals(k)) 的键 k 的映射关系时，38                  * 返回 true。（最多只能有一个这样的映射关系）。39                  */40                 /*41                  * containsValue42                  * boolean containsValue(Object value)如果此映射将一个或多个键映射到指定值，则返回 true。43                  * 更确切地讲，当且仅当此映射至少包含一个对满足 (value==null ? v==null : value.equals(v)) 的值 v 的映射关系时，44                  * 返回 true。对于大多数 Map 接口的实现而言，此操作需要的时间可能与映射大小呈线性关系。                 45                  */46                 /*47                  * 1、首先需要将pattern字符串的各个字符作为key值添加到map中48                  * 判断是否存在这个key值，如果存在这个key值那么判断对应的value值是不是相等49                  */50                 if (map.containsKey(pattern.charAt(i))) { //有这个键值51                     //abcc52                     //deqq53                     //比如上面，map.get(c)=q, word.charAt(3)=q,满足条件54                     if (map.get(pattern.charAt(i))  !=  word.charAt(i)) { //判断当key值相同的时候，value是否相等55                         flag = false;56                         break;57                     }58                 } else { //不包含关键字的时候59                     if (map.containsValue(word.charAt(i))) { //不存在关键字，但是已经存在键值映射，就不符合给定的字符串模式60                         /*abcc61                         meee62                         上面的这种：首先会将a-m、b-e加入map中，然后第三次判断，键c不存在，63                         但是值e已经存在，这是不符合的所以需要剔除这种情况64                         */65                         flag = false;66                         break;67                     }68                     //pattern中的每个字符作为key值，word中的对应的字符作为value值69                     map.put(pattern.charAt(i), word.charAt(i));70                 }71             }72             if (flag)73                 res.add(word);74             map.clear();75         }76         return res;77     }78 }