Find and Replace Pattern - Solution & Explanation
Problem Statement
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 <= 201 <= words.length <= 50words[i].length == pattern.lengthpatternandwords[i]are lowercase English letters.
Approach Overview
Problem Overview: Given a list of words and a pattern, return all words that follow the same letter pattern. Each character in the pattern must map to exactly one character in the word, and the mapping must be bijective (one‑to‑one and onto).
Approach 1: Bijective Mapping Approach (O(n * m) time, O(1) space)
The core idea is enforcing a one-to-one mapping between characters in the pattern and characters in each candidate word. For every word, iterate through its characters and maintain two hash maps: one mapping pattern → word and another mapping word → pattern. If a conflict appears (a pattern character maps to two different letters or two pattern characters map to the same letter), the word is invalid. Because each word is scanned once and hash lookups are constant time, the total complexity is O(n * m), where n is the number of words and m is the word length. This approach relies heavily on hash table lookups and straightforward iteration.
Approach 2: Pattern Encoding Approach (O(n * m) time, O(m) space)
Instead of storing explicit mappings, encode both the pattern and each word into a canonical representation. While iterating through characters, assign each new character the next available index and build a numeric sequence such as [0,1,1] or [0,1,0]. If the encoded pattern matches the encoded word sequence, the structures are identical and the word fits the pattern. For example, the pattern abb becomes [0,1,1]. Any word producing the same encoding follows the same structural pattern. The encoding process runs in O(m) time per word and uses a small map or array to track character indices. This approach works well when dealing with string normalization problems.
Recommended for interviews: The bijective mapping solution is what interviewers typically expect. It clearly demonstrates understanding of one-to-one mappings and practical use of a array iteration with hash tables. Pattern encoding is equally efficient and sometimes shorter to implement, but the bijection check communicates the constraint directly and is easier to reason about during whiteboard discussions.
Approach 1: Bijective Mapping Approach
In this approach, we establish a one-to-one mapping for each letter in the pattern to letters in each word. To do this, we use two maps or dictionaries: one for mapping pattern to word letters and another for mapping word to pattern letters. Both maps are used to ensure that the mapping is bijective (i.e., one-to-one).
This C code defines a function matchesPattern to check if a particular word matches the pattern based on bijective mappings. The primary function findAndReplacePattern iterates over each word, using matchesPattern to verify matches, and stores the matching words.
Complexity
Time Complexity: O(n * m), where n is the number of words and m is the word length.
Space Complexity: O(m), for the maps storing character mappings.
Approach 2: Pattern Encoding Approach
In this approach, we map each character of the string to its first occurrence index in the string. This creates a unique encoding pattern for comparison. Two strings match if they have the same encoding pattern.
This C program calculates an encoded representation for the pattern and each word using indices of first occurrences. It then compares these encodings to determine if a word matches the pattern.
Complexity
Time Complexity: O(n * m), where n is the number of words and m is the word length.
Space Complexity: O(m), for storing encoded strings and maps.
Approach 3: Default Approach
Try this approach in the editor →Complexity Comparison
| Approach | Complexity |
|---|---|
| Bijective Mapping Approach | Time Complexity: O(n * m), where n is the number of words and m is the word length. |
| Pattern Encoding Approach | Time Complexity: O(n * m), where n is the number of words and m is the word length. |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Bijective Mapping Approach | O(n * m) | O(1) | General case; clearly enforces one-to-one character mapping |
| Pattern Encoding Approach | O(n * m) | O(m) | When comparing structural patterns across many strings |
Video Solution
Find and Replace Pattern | Live Coding with Explanation | Leetcode - 890 • Algorithms Made Easy • 7,127 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Find and Replace Pattern easy or hard?
Find and Replace Pattern Python/Java solution
How to solve Find and Replace Pattern in O(n)?
What is the best approach for Find and Replace Pattern?
Is Find and Replace Pattern asked at Google/Amazon/Meta?
What data structure is used in Find and Replace Pattern?
What is the time complexity of Find and Replace Pattern?
Ready to solve this problem?
Practice Find and Replace Pattern with our built-in code editor and test cases.
Practice on FleetCodeTable of Contents
Practice this problem
Open in Editor