# Find and Replace Pattern (Leetcode 890)

Difficulty: Medium Link: Day 21: May Leetcode Challenge

## Problem Description

Given a list of strings `words` and a string `pattern`, return a list of `words[i]` that match `pattern`. You may return the answer in any order.

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.

## Examples

``````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.
``````
``````Input: words = ["a","b","c"], pattern = "a"
Output: ["a","b","c"]
``````

### Constraints

• `1 <= pattern.length <= 20`
• `1 <= words.length <= 50`
• `words[i].length == pattern.length`
• `pattern` and `words[i]` are lowercase English letters.

## Solution

This might look like a version of Rabin Karp pattern matching, however it is used for matching the absolute patterns. What we can think of is creating a bi-directional mapping of every word character to pattern character and vice-versa. This way, we can check if any mapping is incorrect then we can safely say that the word is not following the pattern. To simply our code, we will extract the logic into a helper function for checking if a word matches the pattern. We will iterate over the words and test our eligibility for every word, in the end filtering the list of words who passed the test. To match bi-directional mapping , we will create two [Character:Character] dictionaries and check the result. We also used the zip(_ , _) functional to pair-wise compare the characters in word and pattern.

## Complexity Analysis

• Time Complexity: O(N * K), where N is the number of words, and K is the length of each word.
• Space Complexity: O(N * K), the space used by the answer.