algoadvance

You are provided with a list of strings called words and a single string called pattern. Your task is to find all words in the list that match the pattern. A word matches the pattern if there exists a permutation of letters, such that after relabeling the pattern letters the word matches the exact pattern string.

For instance, if the pattern is “abb” and there is a word “xyz”, “xyz” matches because we can map ‘a’ <-> ‘x’ and ‘b’ <-> ‘y’.

Example

Input: words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb"
Output: ["mee","aqq"]

Constraints

• 1 <= len(pattern) <= 20
• 1 <= len(words[i]) <= 20
• All strings in words and pattern consist of lowercase English letters.

Clarifying Questions

1. Are the lengths of the pattern and each word guaranteed to be the same?
   • Yes, both the pattern and each word are guaranteed to have the same length.
2. Can we have repeating characters in the pattern as well as in the words?
   • Yes, repeating characters are allowed.
3. Should we maintain the order of the words in the output?
   • Yes, the order in which words appear in result should be same as they appear in the input list.

Strategy

To solve this problem, we can use the following approach:

1. Representation Function: Create a helper function pattern_match that constructs a unique representation for a given string based on the order of appearance of characters. For example, the string “abb” would translate to the pattern “0,1,1”.
2. Match Patterns: For each word in the input list, convert it to its pattern representation using the helper function.
3. Comparison: Compare the pattern representation of each word with the given pattern’s representation.
4. Collect Matches: Collect all words that match the pattern.

Here’s the code based on the above strategy:

from typing import List

def findAndReplacePattern(words: List[str], pattern: str) -> List[str]:
    def pattern_match(word: str) -> List[int]:
        m = {}
        return [m.setdefault(c, len(m)) for c in word]
    
    pattern_rep = pattern_match(pattern)
    return [word for word in words if pattern_match(word) == pattern_rep]

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

Time Complexity

• Pattern Matching Function: O(N) for each word where N is the length of the word.
• Overall: O(L * N) where L is the number of words in the list and N is the length of each word (or pattern). This is because we need to apply the pattern matching function to each word.

This approach efficiently solves the given problem within the provided constraints.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?