Watch 10 video solutions for Find and Replace Pattern, a medium level problem involving Array, Hash Table, String. This walkthrough by Algorithms Made Easy has 7,102 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.lengthpattern and words[i] are lowercase English letters.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 | 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 |