Algorithm
Problem Name: 890. Find and Replace Pattern
Problem Link: https://leetcode.com/problems/find-and-replace-pattern/
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.
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
vector<string> findAndReplacePattern(vector<string>& words, string pattern) {
vector<string>res;
for (auto& s: words) {
if (isValid(s, pattern)) {
res.push_back(s);
}
}
return res;
}
bool isValid(string& a, string& b) {
unordered_map < char, char>m, t;
int n = a.size(), l = b.size();
if (n != l) {
return false;
}
for (int i = 0; i < n; ++i) {
if (m.count(a[i]) || t.count(b[i])) {
if (m[a[i]] == b[i] && t[b[i]] == a[i]) {
continue;
} else {
return false;
}
}
m[a[i]] = b[i];
t[b[i]] = a[i];
}
return true;
}
};
class Solution {
public:
vector < string> findAndReplacePattern(vector<string>& words, string pattern) {
vector<string>res;
for (auto& s: words) {
if (normalize(s) == normalize(pattern)) {
res.push_back(s);
}
}
return res;
}
string normalize(string& s) {
unordered_map < char, char>m;
string res;
char c = 'a';
for (auto& x: s) {
if (!m.count(x)) {
m[x] = c++;
}
}
for (auto& x: s) {
res.push_back(m[x]);
}
return res;
}
};
Input
words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb"
Output
["mee","aqq"]
#2 Code Example with Java Programming
Code -
Java Programming
class Solution {
public List findAndReplacePattern(String[] words, String pattern) {
String patternString = getPattern(pattern);
return Arrays.stream(words).filter(e -> getPattern(e).equals(patternString))
.collect(Collectors.toList());
}
private String getPattern(String s) {
StringBuilder sb = new StringBuilder();
Map < Character, Integer> map = new HashMap<>();
int count = 1;
for (char c : s.toCharArray()) {
if (!map.containsKey(c)) {
map.put(c, count++);
}
sb.append(map.get(c));
}
return sb.toString();
}
}
Input
words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb"
Output
["mee","aqq"]
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const findAndReplacePattern = (words, pattern) => {
return words.reduce((acc, item, index) => {
if (compose(words[index], pattern)) acc.push(words[index]);
return acc;
}, []);
function compose(element, pattern) {
const s = new Set();
const m = new Map();
for (let i = 0; i < element.length; i++) {
const e = element[i];
const p = pattern[i];
s.add(e);
if (m.get(p) === undefined) {
m.set(p, e);
} else if (m.get(p) !== e) {
return false;
}
}
return m.size === s.size;
}
};
Input
words = ["a","b","c"], pattern = "a"
Output
["a","b","c"]
#4 Code Example with Python Programming
Code -
Python Programming
class Solution:
def findAndReplacePattern(self, words, pattern):
"""
:type words: List[str]
:type pattern: str
:rtype: List[str]
"""
res = []
for w in words:
mp12, mp21, match = {}, {}, True
for c1, c2 in zip(w, pattern):
if (c1 in mp12 and mp12[c1] != c2) or (c2 in mp21 and mp21[c2] != c1):
match = False
break
mp12[c1], mp21[c2] = c2, c1
if match: res.append(w)
return res
Input
words = ["a","b","c"], pattern = "a"
Output
["a","b","c"]
#5 Code Example with C# Programming
Code -
C# Programming
using System.Collections.Generic;
namespace LeetCode
{
public class _0890_FindAndReplacePattern
{
public IList < string> FindAndReplacePattern(string[] words, string pattern)
{
var result = new List();
foreach (var word in words)
if (Match(word, pattern))
result.Add(word);
return result;
}
private bool Match(string word, string pattern)
{
var map1 = new Dictionary < char, char>();
var map2 = new Dictionary();
for (int i = 0; i < pattern.Length; i++)
{
if (!map1.ContainsKey(pattern[i]))
map1[pattern[i]] = word[i];
if (!map2.ContainsKey(word[i]))
map2[word[i]] = pattern[i];
if (map1[pattern[i]] != word[i] || map2[word[i]] != pattern[i])
return false;
}
return true;
}
}
}
Input
words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb"
Output
["mee","aqq"]