Skip to main content
  1. Problem Solving Solutions/

Find and Replace Pattern LeetCode Solution

·2 mins read
Mayukh Datta
Problem Solving LeetCode
Table of Contents

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.

Link: https://leetcode.com/problems/find-and-replace-pattern/

Solution
#

This problem is similar to the Isomorphic strings problem on LeetCode. We need to check which of the strings present in words array are isomorphic with the pattern string.

Time complexity: \(O(M * N)\), M is the number of words present and K is the length of each word.