Skip to main content

890. Find and Replace Pattern

medium

Filter a list of words to those that match a given letter pattern, where matching means there's a one-to-one letter mapping that turns the pattern into the word. Same two-hash-equality-test trick as Isomorphic Strings, applied per candidate word.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

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.

Constraints

  • 1 <= pattern.length <= 20
  • 1 <= words.length <= 50
  • words[i].length == pattern.length
  • pattern and words[i] are lowercase English letters.

Examples

Example 1

Input
words = ['abc','deq','mee','aqq','dkd','ccc'], pattern = 'abb'
Output
['mee','aqq']

Explanation: 'mee' matches because p('a')='m', p('b')='e'. 'ccc' fails because p would need to map both 'a' and 'b' to 'c'.

Example 2

Input
words = ['a','b','c'], pattern = 'a'
Output
['a','b','c']

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Single map pattern_char -> word_char is not enough; ('abb','ccc') would pass without a reverse check because no letter ever sees a different word-char.

Hint 2

Two-hash equality test: forward map (pattern -> word) AND reverse map (word -> pattern). Both must remain consistent across all indices.

Hint 3

Run the check for each candidate word and collect the ones that pass.

Solution approach

Reveal approach

Run a per-word two-hash equality test. Helper matches(pattern, word): walk the indices in parallel. Maintain pToW and wToP. For each (p, w), if either map has a conflicting entry, return false. Otherwise record both. Return true at the end. The outer pass filters words to those passing matches. This is the same template as Word Pattern and Isomorphic Strings — once you internalize 'two maps in both directions', this family of problems all collapses to that primitive.

Complexity

Time
O(n * m)
Space
O(m)

Related patterns

  • hash-map
  • two-hash-equality-test

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Uber

Practice these live with InterviewChamp.AI

Drill Find and Replace Pattern and Hash Tables problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →