Solution: Find and Replace Pattern
Tags: algorithms, javascript, java, python
Published: 2021-05-21 09:15:17

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/find-and-replace-pattern/discuss/1221188).*

---

#### [Leetcode Problem #890 (*Medium*): Find and Replace Pattern](https://leetcode.com/problems/find-and-replace-pattern/)

---

#### ***Description:***

<br />(*Jump to*: [*Solution Idea*](#idea) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

>
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, ...}.<br>"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:***

<br />(*Jump to*: [*Problem Description*](#description) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

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:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```javascript
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:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```python
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:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```java
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;
        ans.add(word);
    }
}
```

---

#### ***C++ Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```c++
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);
    }
};
```