today's contribution, medium problem, easy regex problem

sherxon · Aug 28, 2018 · 7a60863 · 7a60863
1 parent bc48416
commit 7a60863
Show file tree

Hide file tree

Showing 2 changed files with 69 additions and 0 deletions.
diff --git a/src/problems/Medium.txt b/src/problems/Medium.txt
@@ -3063,3 +3063,30 @@ Note:
 
 1 <= people.length <= 50000
 1 <= people[i] <= limit <= 30000
+
+199) Find and Replace Pattern
+You have a list of words and a pattern, and you want to know which words in words matches the pattern.
+
+A word matches the pattern if there exists a permutation of letters p so that after replacing every letter x in the pattern with p(x), we get the desired word.
+
+(Recall that a permutation of letters is a bijection from letters to letters: every letter maps to another letter, and no two letters map to the same letter.)
+
+Return a list of the words in words that match the given pattern.
+
+You may return the answer in any order.
+
+
+
+Example 1:
+
+Input: words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb"
+Output: ["mee","aqq"]
+Explanation: "mee" matches the pattern because there is a permutation {a -> m, b -> e, ...}.
+"ccc" does not match the pattern because {a -> c, b -> c, ...} is not a permutation,
+since a and b map to the same letter.
+
+
+Note:
+
+1 <= words.length <= 50
+1 <= pattern.length = words[i].length <= 20
diff --git a/src/problems/medium/FIndAndReplacePattern.java b/src/problems/medium/FIndAndReplacePattern.java
@@ -0,0 +1,42 @@
+package problems.medium;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+
+/**
+ * Why Did you create this class? what does it do?
+ */
+public class FIndAndReplacePattern {
+
+    public static void main(String[] args) {
+        System.out.println(findAndReplacePattern(new String[] {
+                "abc", "deq", "mee", "aqq", "dkd", "ccc"
+        }, "abb"));
+    }
+
+    static public List<String> findAndReplacePattern(String[] words, String pattern) {
+        if (words == null || words.length == 0)
+            return new ArrayList<>();
+        List<String> list = new ArrayList<>();
+        for (String s : words) {
+            Map<Character, Character> strValues = new HashMap<>();
+            Map<Character, Character> patterns = new HashMap<>();
+            boolean yes = true;
+            for (int i = 0; i < s.length(); i++) {
+                char patternVal = strValues.getOrDefault(s.charAt(i), pattern.charAt(i));//a
+                char strVal = patterns.getOrDefault(patternVal, s.charAt(i));//d
+                if (strVal != s.charAt(i) || patternVal != pattern.charAt(i)) {
+                    yes = false;
+                    break;
+                }
+                strValues.put(s.charAt(i), patternVal);//d=>a, k->b
+                patterns.put(pattern.charAt(i), strVal); //a=>d, b->k
+            }
+            if (yes)
+                list.add(s);
+        }
+        return list;
+    }
+}