198.md

890. Find and Replace Pattern

Difficulty: 🟡 Medium

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.

Solutions

O(n * m) of solution

Python3

class Solution:
    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:
        def is_match(word, pattern):
            word_to_pattern = {}
            pattern_to_word = {}
            for char_word, char_pattern in zip(word, pattern):
                if char_word not in word_to_pattern and char_pattern not in pattern_to_word:
                    word_to_pattern[char_word] = char_pattern
                    pattern_to_word[char_pattern] = char_word
                if (char_word in word_to_pattern and word_to_pattern[char_word] != char_pattern) or \
                   (char_pattern in pattern_to_word and pattern_to_word[char_pattern] != char_word):
                    return False
            return True

        answer = []
        for word in words:
            if is_match(word, pattern):
                answer.append(word)
        return answer

The solution involves checking each word in the words list to determine if it matches the given pattern. To do this, we'll define a helper function, is_match(word, pattern), that checks if a given word matches the pattern.

Here's how the solution works:

1. Define the is_match(word, pattern) function that takes a word and a pattern as input. Within this function, initialize two dictionaries, word_to_pattern and pattern_to_word, which will store the mapping of characters from the word to the pattern and vice versa.
2. Iterate through each character pair, (char_word, char_pattern), where char_word is a character from the word and char_pattern is a character from the pattern. For each character pair, perform the following steps:
   • If char_word is not in the word_to_pattern dictionary and char_pattern is not in the pattern_to_word dictionary, this means that the mapping of char_word to char_pattern and char_pattern to char_word has not been established yet. In this case, add char_word to word_to_pattern with a value of char_pattern and add char_pattern to pattern_to_word with a value of char_word.
   • If char_word is already in the word_to_pattern dictionary, check if the value associated with char_word is equal to char_pattern. If they are not equal, return False because the mapping is not consistent.
   • If char_pattern is already in the pattern_to_word dictionary, check if the value associated with char_pattern is equal to char_word. If they are not equal, return False because the mapping is not consistent.
3. After iterating through all character pairs, if no inconsistencies are found in the mappings, return True from the is_match function, indicating that the word matches the pattern.
4. In the main part of the solution, initialize an empty list answer to store the words that match the pattern.
5. Iterate through each word in the words list. For each word, call the is_match function with the word and the pattern as arguments. If the function returns True, append the word to the answer list.
6. After iterating through all words, the answer list contains the words that match the pattern. Return the answer list as the final result.

Complexity Analysis

• Time Complexity: The solution iterates through the words list once and performs checks for each character pair in the word and pattern, leading to a time complexity of O(n * m), where n is the number of words and m is the length of the pattern.
• Space Complexity: The solution uses additional space to store the dictionaries word_to_pattern and pattern_to_word, which can have a maximum of 26 lowercase letters as keys and values. Therefore, the space complexity is O(26) ≈ O(1), as it is a constant amount of space.

Summary

The provided solution effectively checks each word in the words list to determine if it matches the given pattern by establishing mappings between characters. It has a time complexity of O(n * m) and a space complexity of O(1), making it efficient for the given constraints.

Another O(n * m) of solution

Python3

class Solution:
    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:
        def to_num_array(word):
            mapping = {}
            return [mapping.setdefault(char, len(mapping)) for char in word]

        numeric_pattern = to_num_array(pattern)
        answer = []
        for word in words:
            if numeric_pattern == to_num_array(word):
                answer.append(word)
        return answer

The solution involves checking each word in the words list to determine if it matches the given pattern. To do this, we'll define a helper function, to_num_array(word), that converts a word into a numeric array based on character mapping. This function will map each character in the word to a unique numeric value, maintaining the order of characters.

Here's how the solution works:

1. Define the to_num_array(word) function that takes a word as input. Within this function, initialize an empty dictionary called mapping. This dictionary will be used to map characters to their corresponding numeric values. Then, iterate through each character, char, in the word and perform the following steps:
   • Check if char exists as a key in the mapping dictionary. If it does, return the corresponding numeric value using mapping[char]. If it does not exist, add char as a key to the mapping dictionary with a value equal to len(mapping). This assigns a unique numeric value to each character in the order they appear.
   • Finally, return a list of numeric values obtained from the mapping for each character in the word. This list represents the numeric array corresponding to the given word.
2. In the main part of the solution, initialize an empty list answer to store the words that match the pattern.
3. Use the to_num_array function to convert the pattern string into a numeric array called numeric_pattern.
4. Iterate through each word in the words list. For each word, convert it into a numeric array using the to_num_array function and store it in a variable called numeric_word.
5. Check if numeric_pattern is equal to numeric_word. If they are equal, it means the word matches the pattern. In this case, append the original word to the answer list.
6. After iterating through all words, the answer list contains the words that match the pattern. Return the answer list as the final result.

Complexity Analysis

• Time Complexity: The solution iterates through each word in the words list and converts each word into a numeric array using the to_num_array function. The conversion takes O(m) time for each word, where m is the length of the word. Therefore, the overall time complexity is O(n * m), where n is the number of words and m is the length of the pattern.

• Space Complexity: The solution uses additional space to store the mapping dictionary, which can have at most 26 lowercase letters as keys and values. Therefore, the space complexity is O(26) ≈ O(1), as it is a constant amount of space. Additionally, the numeric arrays have a space complexity of O(m), where m is the length of the pattern. Overall, the space complexity is O(1).

Summary

The provided solution effectively checks each word in the words list to determine if it matches the given pattern by converting both the pattern and the words into numeric arrays based on character mapping. It has a time complexity of O(n * m) and a space complexity of O(1), making it efficient for the given constraints.

NB: If you want to get community points please suggest solutions in other languages as merge requests.