We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find and Replace Pattern

Number: 926

Difficulty: Medium

Paid? No

Companies: Zomato, Amazon

Problem Description

Given a list of words and a string pattern, return the list of words that match the pattern. A word matches the pattern if there exists a bijective mapping (permutation) of letters from the pattern to the word such that replacing every letter in the pattern with its mapped letter returns the word.

Key Insights

  • The mapping between letters must be one-to-one and onto (bijective).
  • Use two hash maps (or dictionaries): one mapping from the pattern to the word and another from the word to the pattern.
  • For each word, iterate through each character position and verify that both mappings are consistent.
  • If a conflict is detected in either mapping, the word does not match the pattern.

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(m) per word, used for the bidirectional mappings.

Solution

For each word, use a helper function to build two mappings: one from the pattern to the word and one from the word to the pattern. Check character by character that:

  1. If a mapping from a pattern character already exists, it matches the corresponding word character.
  2. If a mapping from a word character already exists, it matches the corresponding pattern character. If both conditions hold for all characters, the word matches the pattern. Otherwise, it does not.

Code Solutions

def findAndReplacePattern(words, pattern):
    # Helper function checks if a single word matches the pattern using bidirectional mapping.
    def matches(word, pattern):
        p_to_w = {}  # Mapping from pattern character to word character
        w_to_p = {}  # Mapping from word character to pattern character
        for p_char, w_char in zip(pattern, word):
            # Check or set the mapping from pattern to word.
            if p_char in p_to_w:
                if p_to_w[p_char] != w_char:
                    return False
            else:
                p_to_w[p_char] = w_char
            # Check or set the mapping from word to pattern.
            if w_char in w_to_p:
                if w_to_p[w_char] != p_char:
                    return False
            else:
                w_to_p[w_char] = p_char
        return True

    result = []
    for word in words:
        # Include the word if it matches the pattern.
        if matches(word, pattern):
            result.append(word)
    return result

# Example usage:
# words = ["abc", "deq", "mee", "aqq", "dkd", "ccc"]
# pattern = "abb"
# print(findAndReplacePattern(words, pattern))
← Back to All Questions