Find and Replace Pattern

Given a list of strings words and a string pattern, return a list of words[i] that match 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.

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. 1 <= pattern.length <= 20
2. 1 <= words.length <= 50
3. words[i].length == pattern.length
4. pattern and words[i] are lowercase English letters.

def find_and_replace_pattern(words: list[str], pattern: str) -> list[str]:
    """Given a list of strings `words` and a string `pattern`, return *a list of* `words[i]` *that match* `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.

    Example:
    ----------
    words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb"
    Output: ["mee","aqq"]
    """
    def match(word, pattern):
        if len(word) != len(pattern):
            return False

        word_to_pattern = {}
        pattern_to_word = {}

        for w, p in zip(word, pattern):
            if w not in word_to_pattern and p not in pattern_to_word:
                word_to_pattern[w] = p
                pattern_to_word[p] = w
            elif w in word_to_pattern and word_to_pattern[w] != p:
                return False
            elif p in pattern_to_word and pattern_to_word[p] != w:
                return False
            elif w not in word_to_pattern or p not in pattern_to_word:
                return False

        return True

    result = []
    for word in words:
        if match(word, pattern):
            result.append(word)

    return result

# Brute Force Solution
# For each word in words, check if it matches the pattern.
# To check if a word matches the pattern, create two dictionaries:
# 1. word_to_pattern: maps characters in the word to characters in the pattern.
# 2. pattern_to_word: maps characters in the pattern to characters in the word.
# Iterate through the word and the pattern simultaneously.
# If a character in the word is not in word_to_pattern and a character in the pattern is not in pattern_to_word, add the mapping to both dictionaries.
# If a character in the word is in word_to_pattern, check if the mapping is consistent.
# If a character in the pattern is in pattern_to_word, check if the mapping is consistent.
# If the lengths of the word and pattern are not equal, return False.
# If the word matches the pattern, add it to the result.

# Optimized Solution
# The optimized solution is the same as the brute force solution because it is already efficient.

# Big O Time Complexity
# O(N * M), where N is the number of words and M is the length of the pattern (or word, since they have the same length).
# The match function iterates through the word and pattern once, which takes O(M) time.
# The find_and_replace_pattern function iterates through the words once, which takes O(N) time.
# Therefore, the overall time complexity is O(N * M).

# Big O Space Complexity
# O(M), where M is the length of the pattern (or word).
# The match function creates two dictionaries, word_to_pattern and pattern_to_word.
# The size of each dictionary is at most M, since there can be at most M unique characters in the word and pattern.
# Therefore, the overall space complexity is O(M).

# Edge Cases
# 1. Empty words list: return empty list
# 2. Empty pattern: if words are also empty strings, return the list of empty string words, otherwise return empty list
# 3. Words with different lengths than the pattern: ignore these words
# 4. Words with the same length as the pattern but do not match: ignore these words
# 5. Words that match the pattern: add these words to the result

# Example Usage
words = ["abc", "deq", "mee", "aqq", "dkd", "ccc"]
pattern = "abb"
result = find_and_replace_pattern(words, pattern)
print(result) # Output: ['mee', 'aqq']

words = ["a", "b", "c"]
pattern = "a"
result = find_and_replace_pattern(words, pattern)
print(result) # Output: ['a', 'b', 'c']

words = ["foo", "bar", "baz"]
pattern = "baz"
result = find_and_replace_pattern(words, pattern)
print(result) # Output: ['baz']

words = []
pattern = "abc"
result = find_and_replace_pattern(words, pattern)
print(result) # Output: []

words = ["", "", ""]
pattern = ""
result = find_and_replace_pattern(words, pattern)
print(result) # Output: ['', '', '']

words = ["abc", "xyz"]
pattern = "mnm"
result = find_and_replace_pattern(words, pattern)
print(result) # Output: []

words = ["aba", "cdc", "eae"]
pattern = "xyx"
result = find_and_replace_pattern(words, pattern)
print(result) # Output: ['aba', 'cdc', 'eae']

words = ["abc", "cba", "xyx", "yxy", "aaa", "bbb"]
pattern = "abc"
result = find_and_replace_pattern(words, pattern)
print(result) # Output: ['abc', 'cba', 'xyx', 'yxy']