# Find and Replace Pattern
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-and-replace-pattern)
Canonical: https://scaleengineer.com/dsa/problems/find-and-replace-pattern
**Data structures:** Array, Hash Table, String
**Companies:** [Zomato](https://scaleengineer.com/companies/zomato)
---
## Problem
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.

**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.

# Approaches
## Single Map with Inefficient Value Check
This approach iterates through each word and compares it with the pattern character by character. A single hash map is used to maintain the mapping from pattern characters to word characters. For a word to match, two conditions must be met for every character pair `(pattern[i], word[i])`:
1. If `pattern[i]` is already in the map, its mapped value must be `word[i]`.
2. If `pattern[i]` is not in the map, we must ensure `word[i]` has not been mapped to by any other pattern character. This is checked by searching through all values in the map.
**Time:** O(N * K^2), where `N` is the number of words and `K` is the length of the pattern. For each of the `N` words, we iterate `K` times. Inside the loop, `map.containsValue()` takes `O(K)` time in the worst case, leading to a total of `O(K^2)` for the `isMatch` function. · **Space:** O(1) auxiliary space. The map stores at most 26 key-value pairs, which is constant.
**Pros:** Conceptually simple to understand.
**Cons:** Inefficient due to the `O(K)` `containsValue` check inside the main loop, leading to a quadratic time complexity relative to the string length.
### Explanation
The main function iterates through the `words` array. For each `word`, it calls a helper function `isMatch(word, pattern)`. The `isMatch` function uses one `HashMap<Character, Character>`. It iterates from `i = 0` to `pattern.length() - 1`. At each position `i`, it gets `pChar = pattern.charAt(i)` and `wChar = word.charAt(i)`. If `map.containsKey(pChar)`, it checks if `map.get(pChar)` equals `wChar`. If not, it's a mismatch, and it returns `false`. If `!map.containsKey(pChar)`, it checks if `map.containsValue(wChar)`. This check is the bottleneck, as it requires iterating through the map's values, taking time proportional to the number of entries in the map. If `wChar` is already a value, it violates the one-to-one mapping rule, so it returns `false`. If both checks pass, a new mapping is added: `map.put(pChar, wChar)`. If the loop finishes, the word is a match.

```java
class Solution {
    public List<String> findAndReplacePattern(String[] words, String pattern) {
        List<String> result = new ArrayList<>();
        for (String word : words) {
            if (isMatch(word, pattern)) {
                result.add(word);
            }
        }
        return result;
    }

    private boolean isMatch(String word, String pattern) {
        Map<Character, Character> map = new HashMap<>();
        for (int i = 0; i < pattern.length(); i++) {
            char pChar = pattern.charAt(i);
            char wChar = word.charAt(i);
            if (map.containsKey(pChar)) {
                if (map.get(pChar) != wChar) {
                    return false;
                }
            } else {
                // This is the inefficient part
                if (map.containsValue(wChar)) {
                    return false;
                }
                map.put(pChar, wChar);
            }
        }
        return true;
    }
}
```
### Algorithm
- 1. Initialize an empty list `result`.
- 2. For each `word` in the input `words` array:
- 3.   Call a helper function `isMatch(word, pattern)`.
- 4.   Inside `isMatch`, create a single `HashMap` to store mappings from pattern characters to word characters.
- 5.   Iterate through the `pattern` and `word` from left to right.
- 6.   For each character `p` from `pattern` and `w` from `word`:
- 7.     If `p` is a key in the map, check if its value is `w`. If not, return `false`.
- 8.     If `p` is not a key, check if `w` exists as a value in the map using `containsValue()`. If it does, return `false`.
- 9.     If both checks pass, add the mapping `p -> w` to the map.
- 10.  If the loop completes, return `true`.
- 11.  If `isMatch` returns `true`, add the `word` to the `result` list.
- 12. Return `result`.

## Normalization to a Canonical Form
A more efficient approach is to transform both the pattern and each word into a "canonical" or "normalized" form. Two strings have the same pattern if and only if their canonical forms are identical. A canonical form can be generated by replacing the first unique character with 'a', the second unique character with 'b', and so on.
**Time:** O(N * K), where `N` is the number of words and `K` is the length of the pattern. Normalizing the pattern takes `O(K)`. Then, for each of the `N` words, we perform a normalization which takes `O(K)` and a string comparison which also takes `O(K)`. · **Space:** O(K) auxiliary space. The `normalize` function requires a `StringBuilder` and a `HashMap`, both of which take space proportional to the number of unique characters (at most `K`). We also store the normalized pattern, which is of length `K`.
**Pros:** Clean and elegant code.; Avoids complex nested logic for checking bijection.
**Cons:** Requires extra space (`O(K)`) to store the normalized strings.; Processes the entire string even if a mismatch occurs early on, which can be less performant in practice than an early-exit strategy.
### Explanation
First, we compute the canonical form of the `pattern` string and store it. Then, we iterate through each `word` in the `words` list. For each `word`, we compute its canonical form. We compare the word's canonical form with the pattern's canonical form. If they are equal, the word matches the pattern, and we add it to our result list. The normalization function works as follows: It uses a map to track characters seen so far and the character they map to in the canonical form. It iterates through the input string, and for each character, if it's the first time seeing it, it maps it to the next available standard character (e.g., 'a', then 'b', ...). It then builds the normalized string using these mappings.

```java
class Solution {
    public List<String> findAndReplacePattern(String[] words, String pattern) {
        List<String> result = new ArrayList<>();
        String normalizedPattern = normalize(pattern);
        for (String word : words) {
            if (normalizedPattern.equals(normalize(word))) {
                result.add(word);
            }
        }
        return result;
    }

    private String normalize(String str) {
        Map<Character, Character> map = new HashMap<>();
        char nextChar = 'a';
        StringBuilder sb = new StringBuilder();
        for (char c : str.toCharArray()) {
            map.putIfAbsent(c, nextChar++);
            sb.append(map.get(c));
        }
        return sb.toString();
    }
}
```
### Algorithm
- 1. Create a helper function `normalize(string)`.
- 2.   Inside `normalize`, use a `HashMap` to store mappings and a `char` variable (e.g., `nextChar = 'a'`) for the canonical representation.
- 3.   Iterate through the input string. For each character, if it's not in the map, map it to `nextChar` and increment `nextChar`.
- 4.   Build and return the new normalized string.
- 5. In the main function, normalize the `pattern` string once.
- 6. Initialize an empty list `result`.
- 7. For each `word` in `words`:
- 8.   Normalize the `word`.
- 9.   If the normalized `word` equals the normalized `pattern`, add the original `word` to `result`.
- 10. Return `result`.

## Two Hash Maps for Efficient Bijection Check
This is a highly efficient approach in terms of both time and space. It checks for a valid pattern match by ensuring a bijective (one-to-one and onto) mapping between the characters of the pattern and the word. This is achieved by using two hash maps: one to map pattern characters to word characters (`p -> w`) and another for the reverse mapping (`w -> p`).
**Time:** O(N * K), where `N` is the number of words and `K` is the length of the pattern. For each of the `N` words, we iterate `K` times. All hash map operations (`put`, `get`, `containsKey`) take `O(1)` time on average. · **Space:** O(1) auxiliary space. The two hash maps store at most 26 characters each (the size of the alphabet), which is a constant amount of space.
**Pros:** Optimal time complexity.; Minimal auxiliary space complexity.; Fails fast: it can stop checking a word as soon as a single character violates the pattern, which can be more efficient in practice than the normalization approach.
**Cons:** The logic involves managing two maps and can be slightly more complex to implement correctly compared to the normalization approach.
### Explanation
The main function iterates through the `words` array, calling a helper `isMatch` function for each `word`. The `isMatch(word, pattern)` function uses two maps, `mapPtoW` and `mapWtoP`. It iterates from `i = 0` to `pattern.length() - 1`. At each position `i`, it gets `pChar = pattern.charAt(i)` and `wChar = word.charAt(i)`. It then checks for two conditions to maintain the bijection:
1. **Forward mapping:** If `pChar` is already in `mapPtoW`, its mapped value must be `wChar`. If `mapPtoW.get(pChar) != wChar`, it's a mismatch.
2. **Reverse mapping:** If `wChar` is already in `mapWtoP`, its mapped value must be `pChar`. If `mapWtoP.get(wChar) != pChar`, it's a mismatch. This check ensures that no two different pattern characters map to the same word character.
If a character pair is new, and the checks pass, the new mappings are added to both maps. If the loop completes without any mismatches, the word is a match. This approach can fail fast as soon as a rule is violated.

```java
class Solution {
    public List<String> findAndReplacePattern(String[] words, String pattern) {
        List<String> result = new ArrayList<>();
        for (String word : words) {
            if (isMatch(word, pattern)) {
                result.add(word);
            }
        }
        return result;
    }

    private boolean isMatch(String word, String pattern) {
        Map<Character, Character> mapPtoW = new HashMap<>();
        Map<Character, Character> mapWtoP = new HashMap<>();
        for (int i = 0; i < pattern.length(); i++) {
            char pChar = pattern.charAt(i);
            char wChar = word.charAt(i);

            if (mapPtoW.containsKey(pChar) && mapPtoW.get(pChar) != wChar) {
                return false;
            }
            if (mapWtoP.containsKey(wChar) && mapWtoP.get(wChar) != pChar) {
                return false;
            }

            mapPtoW.put(pChar, wChar);
            mapWtoP.put(wChar, pChar);
        }
        return true;
    }
}
```
### Algorithm
- 1. Initialize an empty list `result`.
- 2. For each `word` in the input `words` array:
- 3.   Call a helper function `isMatch(word, pattern)`.
- 4.   Inside `isMatch`, create two `HashMaps`: `mapPtoW` for pattern-to-word mapping and `mapWtoP` for word-to-pattern mapping.
- 5.   Iterate through the `pattern` and `word` from left to right.
- 6.   For each character `p` from `pattern` and `w` from `word`:
- 7.     Check if the existing mappings in both maps are consistent with the current `(p, w)` pair.
- 8.     If `p` is in `mapPtoW` but maps to a different character than `w`, return `false`.
- 9.     If `w` is in `mapWtoP` but maps to a different character than `p`, return `false`.
- 10.    If consistent, add/update the mappings in both maps.
- 11.  If the loop completes, return `true`.
- 12.  If `isMatch` returns `true`, add the `word` to the `result` list.
- 13. Return `result`.

# Solutions
### Java

```java
class Solution {
public
  List<String> findAndReplacePattern(String[] words, String pattern) {
    List<String> ans = new ArrayList<>();
    for (String word : words) {
      if (match(word, pattern)) {
        ans.add(word);
      }
    }
    return ans;
  }
private
  boolean match(String s, String t) {
    int[] m1 = new int[128];
    int[] m2 = new int[128];
    for (int i = 0; i < s.length(); ++i) {
      char c1 = s.charAt(i);
      char c2 = t.charAt(i);
      if (m1[c1] != m2[c2]) {
        return false;
      }
      m1[c1] = i + 1;
      m2[c2] = i + 1;
    }
    return true;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<string> findAndReplacePattern(vector<string> &words, string pattern) {
    vector<string> ans;
    auto match = [](string &s, string &t) {
      int m1[128] = {0};
      int m2[128] = {0};
      for (int i = 0; i < s.size(); ++i) {
        if (m1[s[i]] != m2[t[i]])
          return 0;
        m1[s[i]] = i + 1;
        m2[t[i]] = i + 1;
      }
      return 1;
    };
    for (auto &word : words)
      if (match(word, pattern))
        ans.emplace_back(word);
    return ans;
  }
};

```

### Python

```python
class Solution:
    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]: def match (s, t): m1, m2 = [0] * 128, [0] * 128 for i, (a, b) in enumerate(zip(s, t), 1): if m1[ord(a)] != m2[ord(b)]: return False m1[ord(a)] = m2[ord(b)] = i return True return [word for word in words if match (word, pattern)]

```