Find and Replace Pattern solution and explanation
Google
9 more videos on this problem
Find and Replace Pattern | Live Coding with Explanation | Leetcode - 890Algorithms Made Easy · 6:41 · 7K views
Leetcode 890. Find and Replace Pattern || MediumCode with Alisha · 16:06 · 6K views
Find and Replace Pattern | Leetcode 890 | Live coding sessionCoding Decoded · 6:57 · 2K views
Leetcode - Find and Replace Pattern (Python)Timothy H Chang · 6:41 · 1K views
Find and Replace Pattern - LeetCode Problem #890GuyWho LikesCS · 39:16 · 900 views
Find and Replace Pattern | LeetCode 890 | Coders CampCoders Camp · 10:36 · 503 views
Daily Leetcode #850: Jul 29, 2022 - 890. Find and Replace PatternProgramming Live with Larry · 5:01 · 387 views
Leetcode Medium: 890 Find and Replace Patternleetcode · 6:47 · 356 views
Find and Replace Pattern | LeetCode Solution 890Gantavya Malviya · 10:36 · 236 views
LeetCode 890. Find and Replace Pattern Solution Explained - JavaAlgorithms and Data Structures Course · 14:49 · 222 views
The problem
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).
def matchesPattern(word, pattern):
mapPtoW, mapWtoP = {}, {}
for w, p in zip(word, pattern):
if p not in mapPtoW and w not in mapWtoP:
mapPtoW[p] = w
mapWtoP[w] = p
elif mapPtoW.get(p) != w or mapWtoP.get(w) != p:
return False
return True
def findAndReplacePattern(words, pattern):
return [word for word in words if matchesPattern(word, pattern)]import java.util.*;
public class PatternMatch {
public boolean matchesPattern(String word, String pattern) {
Map<Character, Character> mapPtoW = new HashMap<>();
Map<Character, Character> mapWtoP = new HashMap<>();
for (int i = 0; i < pattern.length(); i++) {
char w = word.charAt(i);
char p = pattern.charAt(i);
if (!mapPtoW.containsKey(p) && !mapWtoP.containsKey(w)) {
mapPtoW.put(p, w);
mapWtoP.put(w, p);
} else if (!Objects.equals(mapPtoW.get(p), w) || !Objects.equals(mapWtoP.get(w), p)) {
return false;
}
}
return true;
}
public List<String> findAndReplacePattern(String[] words, String pattern) {
List<String> result = new ArrayList<>();
for (String word : words) {
if (matchesPattern(word, pattern)) {
result.add(word);
}
}
return result;
}
}#include <vector>
#include <string>
#include <unordered_map>
using namespace std;
bool matchesPattern(const string& word, const string& pattern) {
unordered_map<char, char> mapPtoW;
unordered_map<char, char> mapWtoP;
for (int i = 0; i < pattern.size(); ++i) {
char w = word[i];
char p = pattern[i];
if (mapPtoW.find(p) == mapPtoW.end() && mapWtoP.find(w) == mapWtoP.end()) {
mapPtoW[p] = w;
mapWtoP[w] = p;
}
else if (mapPtoW[p] != w || mapWtoP[w] != p) {
return false;
}
}
return true;
}
vector<string> findAndReplacePattern(const vector<string>& words, const string& pattern) {
vector<string> result;
for (const string& word : words) {
if (matchesPattern(word, pattern)) {
result.push_back(word);
}
}
return result;
}function matchesPattern(word, pattern) {
const mapPtoW = new Map();
const mapWtoP = new Map();
for (let i = 0; i < pattern.length; i++) {
const w = word[i];
const p = pattern[i];
if (!mapPtoW.has(p) && !mapWtoP.has(w)) {
mapPtoW.set(p, w);
mapWtoP.set(w, p);
} else if (mapPtoW.get(p) !== w || mapWtoP.get(w) !== p) {
return false;
}
}
return true;
}
function findAndReplacePattern(words, pattern) {
return words.filter(word => matchesPattern(word, pattern));
}#include <stdio.h>
#include <stdbool.h>
#include <string.h>
bool matchesPattern(char* word, char* pattern) {
char mapPtoW[128] = {0};
char mapWtoP[128] = {0};
for (int i = 0; i < strlen(pattern); i++) {
char w = word[i];
char p = pattern[i];
if (!mapPtoW[p] && !mapWtoP[w]) {
mapPtoW[p] = w;
mapWtoP[w] = p;
}
else if (mapPtoW[p] != w || mapWtoP[w] != p) {
return false;
}
}
return true;
}
char** findAndReplacePattern(char** words, int wordsSize, char* pattern, int* returnSize) {
char** result = malloc(wordsSize * sizeof(char*));
int resIndex = 0;
for (int i = 0; i < wordsSize; i++) {
if (matchesPattern(words[i], pattern)) {
result[resIndex++] = words[i];
}
}
*returnSize = resIndex;
return result;
}using System;
using System.Collections.Generic;
using System.Linq;
public class PatternMatcher {
public bool MatchesPattern(string word, string pattern) {
var mapPtoW = new Dictionary<char, char>();
var mapWtoP = new Dictionary<char, char>();
for (int i = 0; i < pattern.Length; i++) {
char w = word[i];
char p = pattern[i];
if (!mapPtoW.ContainsKey(p) && !mapWtoP.ContainsKey(w)) {
mapPtoW[p] = w;
mapWtoP[w] = p;
} else if (mapPtoW[p] != w || mapWtoP[w] != p) {
return false;
}
}
return true;
}
public List<string> FindAndReplacePattern(string[] words, string pattern) {
return words.Where(word => MatchesPattern(word, pattern)).ToList();
}
}This Python code leverages dictionaries to store character mappings from pattern to word and vice versa. The function matchesPattern is a helper used within findAndReplacePattern to filter out non-matching words.
Time Complexity: O(n * m), where n is the number of words and m is the word length.
Space Complexity: O(m), for the dictionaries 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.
def encodePattern(s):
map = {}
encoded = []
index = 0
for c in s:
if c not in map:
map[c] = index
index += 1
encoded.append(str(map[c]))
return ''.join(encoded)
def findAndReplacePattern(words, pattern):
encodedPattern = encodePattern(pattern)
return [word for word in words if encodePattern(word) == encodedPattern]import java.util.*;
public class PatternMatch {
private String encodePattern(String str) {
Map<Character, Integer> map = new HashMap<>();
StringBuilder result = new StringBuilder();
int index = 0;
for (char c : str.toCharArray()) {
if (!map.containsKey(c)) {
map.put(c, ++index);
}
result.append(map.get(c));
}
return result.toString();
}
public List<String> findAndReplacePattern(String[] words, String pattern) {
List<String> result = new ArrayList<>();
String encodedPattern = encodePattern(pattern);
for (String word : words) {
if (encodePattern(word).equals(encodedPattern)) {
result.add(word);
}
}
return result;
}
}#include <vector>
#include <string>
#include <unordered_map>
using namespace std;
string encodePattern(const string& str) {
unordered_map<char, int> map;
string result;
int index = 0;
for (char c : str) {
if (map.find(c) == map.end()) {
map[c] = ++index;
}
result += to_string(map[c]);
}
return result;
}
vector<string> findAndReplacePattern(const vector<string>& words, const string& pattern) {
vector<string> result;
string encodedPattern = encodePattern(pattern);
for (const string& word : words) {
if (encodePattern(word) == encodedPattern) {
result.push_back(word);
}
}
return result;
}function encodePattern(str) {
const map = new Map();
let encoded = '';
let index = 0;
for (const char of str) {
if (!map.has(char)) {
map.set(char, index++);
}
encoded += map.get(char);
}
return encoded;
}
function findAndReplacePattern(words, pattern) {
const encodedPattern = encodePattern(pattern);
return words.filter(word => encodePattern(word) === encodedPattern);
}#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char* encodePattern(const char* str) {
int map[128] = {0};
int size = strlen(str);
char* encoded = (char*)malloc(size + 1);
int index = 0;
for (int i = 0; i < size; i++) {
if (!map[(int)str[i]]) {
map[(int)str[i]] = ++index;
}
encoded[i] = '0' + map[(int)str[i]];
}
encoded[size] = '\0';
return encoded;
}
char** findAndReplacePattern(char** words, int wordsSize, char* pattern, int* returnSize) {
char** result = malloc(wordsSize * sizeof(char*));
int resIndex = 0;
char* encodedPattern = encodePattern(pattern);
for (int i = 0; i < wordsSize; i++) {
char* encodedWord = encodePattern(words[i]);
if (strcmp(encodedPattern, encodedWord) == 0) {
result[resIndex++] = words[i];
}
free(encodedWord);
}
free(encodedPattern);
*returnSize = resIndex;
return result;
}using System;
using System.Collections.Generic;
using System.Linq;
public class PatternMatcher {
private string EncodePattern(string str) {
var map = new Dictionary<char, int>();
var encoded = new List<int>();
int index = 0;
foreach (char c in str) {
if (!map.ContainsKey(c)) {
map[c] = index++;
}
encoded.Add(map[c]);
}
return string.Join("", encoded);
}
public List<string> FindAndReplacePattern(string[] words, string pattern) {
string encodedPattern = EncodePattern(pattern);
return words.Where(word => EncodePattern(word) == encodedPattern).ToList();
}
}In this Python implementation, the encodePattern function maps each character to its first occurrence index, creating a consistent way to compare pattern and words.
Time Complexity: O(n * m), where n is the number of words and m is the word length.
Space Complexity: O(m), for storing encodings and mappings.
Approach 3: Default Approach
function findAndReplacePattern(words: string[], pattern: string): string[] {
return words.filter(word => {
const map1 = new Map<string, number>();
const map2 = new Map<string, number>();
for (let i = 0; i < word.length; i++) {
if (map1.get(word[i]) !== map2.get(pattern[i])) {
return false;
}
map1.set(word[i], i);
map2.set(pattern[i], i);
}
return true;
});
}func findAndReplacePattern(words []string, pattern string) []string {
match := func(s, t string) bool {
m1, m2 := make([]int, 128), make([]int, 128)
for i := 0; i < len(s); i++ {
if m1[s[i]] != m2[t[i]] {
return false
}
m1[s[i]] = i + 1
m2[t[i]] = i + 1
}
return true
}
var ans []string
for _, word := range words {
if match(word, pattern) {
ans = append(ans, word)
}
}
return ans
}use std::collections::HashMap;
impl Solution {
pub fn find_and_replace_pattern(words: Vec<String>, pattern: String) -> Vec<String> {
let pattern = pattern.as_bytes();
let n = pattern.len();
words
.into_iter()
.filter(|word| {
let word = word.as_bytes();
let mut map1 = HashMap::new();
let mut map2 = HashMap::new();
for i in 0..n {
if map1.get(&word[i]).unwrap_or(&n) != map2.get(&pattern[i]).unwrap_or(&n) {
return false;
}
map1.insert(word[i], i);
map2.insert(pattern[i], i);
}
true
})
.collect()
}
}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 | – |
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 |
Frequently asked questions
Is Find and Replace Pattern easy or hard?
Find and Replace Pattern is classified as a Medium problem. The difficulty comes from enforcing bijective mappings correctly and handling conflicts while scanning strings. Once the mapping strategy is understood, the implementation is straightforward.
Find and Replace Pattern Python/Java solution
Python and Java implementations typically use dictionaries or HashMaps to store the forward and reverse character mappings. Each word is checked by iterating through characters and validating the mapping constraints in O(m) time.
How to solve Find and Replace Pattern in O(n)?
The problem cannot be solved in strict O(n) because each word must be inspected character by character. The best achievable complexity is O(n * m), where m is the length of each word. Using hash maps or pattern encoding keeps each comparison linear in the word length.
What is the best approach for Find and Replace Pattern?
The bijective mapping approach is the most common solution. It uses two hash tables to ensure a one-to-one mapping between pattern characters and word characters. Each word is scanned once, giving O(n * m) time complexity where n is the number of words and m is the word length.
Is Find and Replace Pattern asked at Google/Amazon/Meta?
Pattern-matching and bijective mapping problems appear frequently in interviews at companies like Google, Amazon, and Meta. Variants test understanding of hash tables, string normalization, and one-to-one character mapping constraints.
What data structure is used in Find and Replace Pattern?
Hash tables are the primary data structure. They track mappings between pattern characters and word characters to enforce a bijection. Some solutions also use arrays or dictionaries to build encoded pattern representations.
What is the time complexity of Find and Replace Pattern?
The optimal solutions run in O(n * m) time. Each of the n words is checked against the pattern by iterating through its m characters with constant-time hash lookups. Space complexity is O(1) or O(m) depending on the mapping strategy.