Merge pull request gzc426#7 from symkmk/symkmk-patch-4

symkmk · web-flow · commit b0c4501c1cc4 · 2018-12-03T08:24:13.000-06:00
Create 妮可.md
diff --git a/2018.11.30-leetcode890/妮可.md b/2018.11.30-leetcode890/妮可.md
@@ -0,0 +1,87 @@
+```java
+package sy181203;
+
+import java.util.ArrayList;
+import java.util.List;
+
+/**
+ * @author suyuan
+ * 
+你有一个单词列表 words 和一个模式  pattern，你想知道 words 中的哪些单词与模式匹配。
+
+如果存在字母的排列 p ，使得将模式中的每个字母 x 替换为 p(x) 之后，
+我们就得到了所需的单词，那么单词与模式是匹配的。
+
+（回想一下，字母的排列是从字母到字母的双射：每个字母映射到另一个字母，没有两个字母映射到同一个字母。）
+
+返回 words 中与给定模式匹配的单词列表。
+
+你可以按任何顺序返回答案。
+
+ 
+
+示例：
+
+输入：words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb"
+输出：["mee","aqq"]
+解释：
+"mee" 与模式匹配，因为存在排列 {a -> m, b -> e, ...}。
+"ccc" 与模式不匹配，因为 {a -> c, b -> c, ...} 不是排列。
+因为 a 和 b 映射到同一个字母。
+ 
+
+提示：
+
+1 <= words.length <= 50
+1 <= pattern.length = words[i].length <= 20
+
+ */
+public class leetcode_890查找和替换模式
+{
+
+	public static void main(String[] args)
+	{
+		String[] wordsStrings= {"ddd","abc","deq","mee","aqq","dkd","ccc"};
+		 String pattern = "abb";
+		 System.out.println(findAndReplacePattern(wordsStrings, pattern));
+
+	}
+
+	 public static  List<String> findAndReplacePattern(String[] words, String pattern) 
+	 {
+		 List<String> list=new ArrayList<String>();
+		 for(int i=0;i<words.length;i++)
+		 {
+			 if(words[i].length()==pattern.length())
+			 {
+				 if(isMatch(words[i], pattern))
+					 list.add(words[i]);
+			 }
+		 }
+		 return list;
+	 }
+	 
+	 public static boolean isMatch(String word,String pattern)
+	 {
+		 //不用map,弄个布隆过滤器,双射
+		 //直接映射char对应的int值,就不用存数值了
+		 int [] map=new int[128];
+		 int [] isUse=new int[128];
+		 for(int i=0;i<word.length();i++)
+		 {
+			 int p=pattern.charAt(i);
+			 int w=word.charAt(i);
+			 if(map[p]==0 && isUse[w]==0)//没有匹配过
+			 {
+				 map[p]=w;
+				 isUse[w]=1;
+			 }
+			 else if (map[p]!=w) {
+				return false;
+			}
+		 }
+		 return true;
+	 }
+	 
+}
+```
