Find and Replace Pattern — Solution in Python, Java & C++
Find and Replace Pattern solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Find and Replace Pattern is a medium coding problem on strings and hash table, asked in Amazon, Google and Adobe interviews.
- Difficulty: Medium
- Topics: Strings, Hash Table
- Asked at: Amazon, Google, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A word matches a pattern when there is a one-to-one letter substitution turning the pattern into the word — every pattern letter always maps to the same word letter, and no two pattern letters map to the same word letter.
Return every word in words that matches pattern, keeping the original order.
Example 1
Input: words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb"
Output: ["mee","aqq"]
Explanation: "mee" works with a->m and b->e; "dkd" fails because the pattern needs b->k and b->d at once.
Example 2
Input: words = ["kata","duel","rank"], pattern = "abcd"
Output: ["duel","rank"]
Explanation: "kata" repeats a, which "abcd" does not.
Example 3
Input: words = ["aa","bb","ab"], pattern = "cc"
Output: ["aa","bb"]
Constraints
1 <= pattern.length <= 201 <= words.length <= 50words[i].length == pattern.lengthAll strings consist of lowercase English letters.
Hints for Find and Replace Pattern
Hint 1
One map is not enough —
"abc"would 'match'"aaa"if you only check one direction.Hint 2
Keep two maps: pattern letter to word letter and word letter back to pattern letter.
Hint 3
A contradiction in either direction rejects the word immediately.
How to solve Find and Replace Pattern
A one-to-one substitution is a bijection, and a bijection is exactly two consistent maps — one in each direction. Checking both is what rules out two pattern letters collapsing onto the same word letter.
Approach
- For each word, walk the positions with two empty maps.
- At position
i, bindword[i] -> pattern[i]andpattern[i] -> word[i], rejecting the word if either binding contradicts an existing one. - Keep the word if the walk finishes without a contradiction.
Why it works
The forward map enforces that a pattern letter never maps to two different word letters; the backward map enforces injectivity, so two pattern letters can never share a word letter. Together they are precisely the definition of a permutation of the alphabet restricted to the letters used.
Complexity
- Time —
O(n · m) for n words of length m - Space —
O(1) — at most 26 entries per map
Pitfalls
- Checking only one direction accepts
"aaa"for pattern"abc". - Reusing the maps between words leaks bindings from the previous word.
Reference solution
Python
from typing import List
def findAndReplacePattern(words: List[str], pattern: str) -> List[str]:
def ok(w: str) -> bool:
fwd, back = {}, {}
for a, b in zip(w, pattern):
if fwd.setdefault(a, b) != b:
return False
if back.setdefault(b, a) != a:
return False
return True
return [w for w in words if ok(w)]Java
public static String[] findAndReplacePattern(String[] words, String pattern) {
List<String> out = new ArrayList<>();
for (String w : words) {
if (w.length() != pattern.length()) continue;
int[] fwd = new int[128];
int[] back = new int[128];
boolean ok = true;
for (int i = 0; i < w.length(); i++) {
char a = w.charAt(i), b = pattern.charAt(i);
if (fwd[a] == 0) fwd[a] = b;
else if (fwd[a] != b) { ok = false; break; }
if (back[b] == 0) back[b] = a;
else if (back[b] != a) { ok = false; break; }
}
if (ok) out.add(w);
}
return out.toArray(new String[0]);
}C++
vector<string> findAndReplacePattern(vector<string>& words, string pattern) {
vector<string> out;
for (const string& w : words) {
if (w.size() != pattern.size()) continue;
vector<char> fwd(128, 0), back(128, 0);
bool ok = true;
for (size_t i = 0; i < w.size(); i++) {
char a = w[i], b = pattern[i];
if (!fwd[(int) a]) fwd[(int) a] = b;
else if (fwd[(int) a] != b) { ok = false; break; }
if (!back[(int) b]) back[(int) b] = a;
else if (back[(int) b] != a) { ok = false; break; }
}
if (ok) out.push_back(w);
}
return out;
}JavaScript
var findAndReplacePattern = function(words, pattern) {
var ok = function(w) {
if (w.length !== pattern.length) return false;
var fwd = {}, back = {};
for (var i = 0; i < w.length; i++) {
var a = w.charAt(i), b = pattern.charAt(i);
if (fwd[a] === undefined) fwd[a] = b;
else if (fwd[a] !== b) return false;
if (back[b] === undefined) back[b] = a;
else if (back[b] !== a) return false;
}
return true;
};
var out = [];
for (var j = 0; j < words.length; j++) {
if (ok(words[j])) out.push(words[j]);
}
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Hashing: Hash Maps and Hash Sets