#890

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Find and Replace Pattern

Identify all words matching a given pattern by checking consistent letter mappings using hash tables and array scanning techniques.

array hash table string

Problem Statement

Given a list of lowercase strings 'words' and a string 'pattern', return all words that can be obtained by consistently replacing each letter in 'pattern' with a unique letter. Words may be returned in any order, but each mapping must be a bijection, meaning no two letters in the pattern map to the same letter in a word.

A word matches the pattern if there exists a permutation of letters such that replacing each letter in 'pattern' with its mapped letter produces the word exactly. Ensure that all letters are mapped uniquely, preserving the one-to-one correspondence required by the pattern.

Examples

Example 1

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

Output: ["mee","aqq"]

"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"]

Example details omitted.

Constraints

1 <= pattern.length <= 20
1 <= words.length <= 50
words[i].length == pattern.length
pattern and words[i] are lowercase English letters.

Solution Approach

Scan Each Word with Two Hash Tables

Iterate over every word in the list, using one hash table to map pattern letters to word letters and another to verify the inverse mapping. If any mapping conflicts occur, the word cannot match the pattern.

Check Bijective Mapping During Iteration

For each character position, confirm that the current letter of the word corresponds to the correct mapped letter from the pattern and vice versa. Any violation immediately discards the word.

Collect Valid Words

After scanning each word and verifying the mapping consistency, append words that satisfy the bijective mapping condition to the result list. Return this list as the final output.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n * m) where n is the number of words and m is the length of the pattern, since each word is scanned once. Space complexity is O(m) for the hash tables storing character mappings for each word.

What Interviewers Usually Probe

Check if candidates are creating both forward and reverse mappings correctly.
Watch for confusion between bijective and non-bijective letter replacement.
Notice if array scanning is done without efficient hash lookups.

Common Pitfalls or Variants

Common pitfalls

Mapping two different pattern letters to the same word letter, violating bijection.
Forgetting to check the inverse mapping from word letters back to pattern letters.
Assuming words of different lengths than pattern can match without validation.

Follow-up variants

Find words that match a pattern ignoring repeated letters, relaxing bijection constraint.
Return the indices of words matching the pattern instead of the words themselves.
Apply the pattern matching on uppercase letters or mixed-case strings.

FAQ

What does it mean for a word to match the pattern in Find and Replace Pattern?

A word matches if each letter in the pattern can be replaced by a unique letter in the word to reproduce it exactly, forming a bijection.

Can words of different lengths match the pattern?

No, only words with the same length as the pattern can potentially match, since each letter must correspond one-to-one.

How does using hash tables help in this problem?

Hash tables allow quick checks of forward and reverse mappings between pattern letters and word letters, ensuring bijection without scanning repeatedly.

What happens if two letters in the pattern map to the same letter in a word?

The word is invalid because bijection requires each pattern letter to map to a unique letter in the word.

Is the order of the output words important?

No, words can be returned in any order as long as they satisfy the bijective pattern mapping.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:
        def match(s, t):
            m1, m2 = [0] * 128, [0] * 128
            for i, (a, b) in enumerate(zip(s, t), 1):
                if m1[ord(a)] != m2[ord(b)]:
                    return False
                m1[ord(a)] = m2[ord(b)] = i
            return True

        return [word for word in words if match(word, pattern)]

Continue Practicing

#893 groups of special equivalent strings #916 word subsets #929 unique email addresses