{x}
blog image

Find and Replace Pattern

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.

Solution Explanation:

The problem asks to find all words from a given list that match a specific pattern. A word matches the pattern if there's a permutation of letters that transforms the pattern into the word. This means each letter in the pattern maps to a unique letter in the word, and vice-versa.

The core idea of the solution is to create a mapping between characters in the pattern and characters in the word. We use two maps (or arrays as in some implementations) to track this mapping. If at any point, we find a conflict (a character in the pattern maps to multiple characters in the word, or vice versa), we know the word doesn't match the pattern.

Algorithm:

  1. match(s, t) function: This helper function compares a word (s) with the pattern (t).
  2. Initialization: Two integer arrays m1 and m2 (or maps in some languages) are created. m1[i] stores the mapped value for character i from s, similarly m2[i] for t. We initialize them with 0.
  3. Iteration: The code iterates through each character pair (a, b) from s and t.
  4. Mapping Check: It checks if the mappings are consistent. If m1[a] is different from m2[b], it means we have a conflict, and the function returns False (or 0).
  5. Mapping Update: If no conflict, m1[a] and m2[b] are updated with a unique value (i + 1). This ensures that each character maps to a unique value.
  6. Main Function: The main function iterates through each word in the input list words. For each word, it calls the match function. If match returns True, the word is added to the result list.

Time and Space Complexity Analysis:

  • Time Complexity: O(M * N), where M is the number of words and N is the length of each word (and the pattern). The nested loops iterate through the characters of each word and the pattern.

  • Space Complexity: O(1). The space used by the m1 and m2 arrays (or maps) is constant because the size of the alphabet is fixed (26 lowercase English letters).

Code Explanation (using Python as an example):

class Solution:
    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:
        def match(s, t):
            m1, m2 = [0] * 128, [0] * 128 #using ASCII values for characters
            for i, (a, b) in enumerate(zip(s, t), 1): #enumerate starts from 1 for mapping
                if m1[ord(a)] != m2[ord(b)]:  #check if mappings are consistent
                    return False
                m1[ord(a)] = m2[ord(b)] = i  #update mappings
            return True
 
        return [word for word in words if match(word, pattern)] #filter words that match

The Python code leverages list comprehension for a concise implementation. The match function efficiently uses integer arrays (acting as hash maps) to check for consistent character mappings. The ord() function converts characters to their ASCII values, allowing us to use them as indices in the arrays.

The other language solutions follow a similar structure and logic, adapting the data structures and syntax as needed for their respective languages. The core algorithm remains the same.