## DEV Community is a community of 891,295 amazing developers

We're a place where coders share, stay up-to-date and grow their careers. # Solution: Find and Replace Pattern

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

#### Description:

(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

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:

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.
Example 2:
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.

#### Idea:

(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

Right away, we can realize that if we can remap characters in an attempt to match the pattern, it doesn't actually matter which characters map to other characters, just that the locations are consistent.

At this point, then, the goal is to make the comparison as easy as possible. To do that, we can reimagine the words as an alphabetic sequence, where the first new character we come across is always masked to "a", the second to "b", and so on. If we apply this same process to the pattern first, then it should be much easier to compare the words to the pattern.

First, we can define a helper function to translate characters for us. We'll have to create a map or array structure (codex) to keep track of the character mapping for a given word. The translate function will then check to see if the character has already been mapped, and if so, return its mapped value. If not, it assigns it the next unused alphabetic value.

We can then easily translate the pattern into a cipher mask which we can then compare to each word in words using another helper function. The compare function will clear the codex for each word, then we can compare each character of word to the corresponding character in cipher. If at any time we fail to match, we can quickly return out of the comparison and continue with the next word. If the translated word fully matches cipher, it can be added to our answer array (ans).

Then we can return ans once we're done.

• Time Complexity: O(N * M) where N is the length of words and M is the length of each word/pattern
• Space Complexity: O(M) for the codex
• or O(N + M) if you count the space of the output (ans)

#### Javascript Code:

``````var findAndReplacePattern = function(words, pattern) {
let ans = [], codex = new Map()
const translate = char => {
if (!codex.has(char))
codex.set(char, String.fromCharCode(97 + codex.size))
return codex.get(char)
}
const compare = word => {
codex.clear()
for (let i = 0; i < word.length; i++)
if (translate(word[i]) !== cipher[i])
return
ans.push(word)
}
let cipher = new Array(pattern.length)
for (let i = 0; i < pattern.length; i++)
cipher[i] = translate(pattern.charAt(i))
words.forEach(compare)
return ans
};
``````

#### Python Code:

``````class Solution:
def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:
ans, codex = [], defaultdict()
def translate(c: str) -> str:
if c not in codex:
codex[c] = chr(97 + len(codex))
return codex[c]
def compare(word: str) -> None:
codex.clear()
for i in range(len(word)):
if translate(word[i]) != cipher[i]:
return
ans.append(word)
cipher = [translate(c) for c in pattern]
for word in words:
compare(word)
return ans
``````

#### Java Code:

``````class Solution {
List<String> ans;
Map<Character, Character> codex;
char[] cipher;

public List<String> findAndReplacePattern(String[] words, String pattern) {
ans = new ArrayList<>();
codex = new HashMap<>();
cipher = pattern.toCharArray();
for (int i = 0; i < pattern.length(); i++)
cipher[i] = translate(cipher[i]);
for (String word : words) compare(word);
return ans;
}
private char translate(char c) {
if (!codex.containsKey(c))
codex.put(c, (char)(97 + codex.size()));
return codex.get(c);
}
private void compare(String word) {
codex.clear();
for (int i = 0; i < word.length(); i++)
if (translate(word.charAt(i)) != cipher[i]) return;
}
}
``````

#### C++ Code:

``````class Solution {
public:
vector<string> findAndReplacePattern(vector<string>& words, string pattern) {
ans.resize(0);
codex.clear();
cipher = pattern;
for (int i = 0; i < pattern.size(); i++)
cipher[i] = translate(cipher[i]);
for (auto& word : words) compare(word);
return ans;
}
private:
vector<string> ans;
unordered_map<char, char> codex;
string cipher;
char translate(char& c) {
if (codex.find(c) == codex.end())
codex[c] = (char)(97 + codex.size());
return codex[c];
}
void compare(string& word) {
codex.clear();
for (int i = 0; i < word.length(); i++)
if (translate(word[i]) != cipher[i]) return;
ans.push_back(word);
}
};
``````

## Discussion (1) Vitaliy Yanchuk • Edited on

Version in ruby.
I decided to use the incoming pattern as a cipher, not sure how does the middleware cipher add up to performance

``````def find_and_replace_pattern(words, pattern)
matches_pattern = ->(word) {
mapping = {}
word.chars.each.with_index do |letter, index|
if (matcher = mapping[letter])
return if pattern[index] != matcher
else
matcher = pattern[index]
return if mapping.invert.key?(matcher)
mapping[letter] = matcher
end
end

true
}

words.select(&matches_pattern)
end

``````