Find and Replace Pattern

Problem Description

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.

Key Insights

• Each unique character in the pattern must map to a unique character in the matching word.
• The length of the pattern and the word must be the same for a match.
• A bijection (one-to-one mapping) is required between the characters in the pattern and the characters in the matching word.
• We can use a hash table (dictionary) to track the mapping of characters for both the pattern and the word.

Space and Time Complexity

Time Complexity: O(n * m), where n is the number of words and m is the length of the pattern. Space Complexity: O(1), since the maximum number of unique characters is constant (26 for lowercase English letters).

Solution

To solve the problem, we will iterate through each word in the words list and check if it matches the pattern. The solution involves:

1. Using a hash table (dictionary) to store the mapping of characters from the pattern to characters in the word.
2. Another hash table to ensure that each character in the word maps back to a unique character in the pattern.
3. For each character in the pattern and the corresponding character in the word, we will establish the mappings and check for consistency.
4. If the mappings are consistent for the entire length of the pattern, we add the word to the result list.

Code Solutions