In this guide, you will get 890. Find and Replace Pattern LeetCode Solution with the best time and space complexity. The solution to Find and Replace Pattern problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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 <= 20
1 <= words.length <= 50
words[i].length == pattern.length
pattern and words[i] are lowercase English letters.
890. Find and Replace Pattern LeetCode Solution in C++
class Solution {
public:
vector<string> findAndReplacePattern(vector<string>& words, string pattern) {
vector<string> ans;
for (const string& word : words)
if (isIsomorphic(word, pattern))
ans.push_back(word);
return ans;
}
private:
bool isIsomorphic(const string& w, const string& p) {
vector<int> map_w(128);
vector<int> map_p(128);
for (int i = 0; i < w.length(); ++i) {
if (map_w[w[i]] != map_p[p[i]])
return false;
map_w[w[i]] = i + 1;
map_p[p[i]] = i + 1;
}
return true;
}
}; /* code provided by PROGIEZ */
890. Find and Replace Pattern LeetCode Solution in Java
class Solution {
public List<String> findAndReplacePattern(String[] words, String pattern) {
List<String> ans = new ArrayList<>();
for (final String word : words)
if (isIsomorphic(word, pattern))
ans.add(word);
return ans;
}
private boolean isIsomorphic(final String w, final String p) {
Map<Character, Integer> map_w = new HashMap<>();
Map<Character, Integer> map_p = new HashMap<>();
for (Integer i = 0; i < w.length(); ++i)
if (map_w.put(w.charAt(i), i) != map_p.put(p.charAt(i), i))
return false;
return true;
}
} // code provided by PROGIEZ
890. Find and Replace Pattern LeetCode Solution in Python
class Solution:
def findAndReplacePattern(self, words: list[str], pattern: str) -> list[str]:
def isIsomorphic(w: str, p: str) -> bool:
return [*map(w.index, w)] == [*map(p.index, p)]
return [word for word in words if isIsomorphic(word, pattern)] # code by PROGIEZ
