Find and Replace Pattern

Find and Replace Pattern

What is this problem about?

The Find and Replace Pattern interview question asks you to filter a list of words to find those that match a given pattern. A word matches a pattern if there is a permutation of characters such that replacing every character in the pattern with its mapped character results in the word. This is essentially a check for isomorphism—the structure of the mapping must be one-to-one (bijective).

Why is this asked in interviews?

Amazon and Zomato use this problem to test your understanding of character mapping and the Hash Table interview pattern. It evaluation whether you can implement a two-way (bi-directional) mapping to ensure that two different characters in the pattern don't map to the same character in the word, and vice versa. It’s a test of logical consistency and efficient string processing.

Algorithmic pattern used

This problem uses Bi-directional Mapping with two Hash Maps (or one map and a "seen" set).

1. For each word, create two maps: pattern_to_word and word_to_pattern.
2. Iterate through both strings character by character.
3. For each pair $(p, w)$:
   • If $p$ is mapped to something other than $w$, fail.
   • If $w$ is mapped to something other than $p$, fail.
   • Otherwise, establish the mapping if it doesn't exist.
4. If the loop finishes, the word matches the pattern.

Example explanation

Pattern: "abb", Word: "mee"

1. 'a' $o$ 'm'. Map: {a: m, m: a}.
2. 'b' $o$ 'e'. Map: {a: m, m: a, b: e, e: b}.
3. 'b' $o$ 'e'. Already exists. Consistent. Result: Match.

Pattern: "abb", Word: "xyz"

1. 'a' $o$ 'x'.
2. 'b' $o$ 'y'.
3. 'b' $o$ 'z'. Error! 'b' was already mapped to 'y'. Result: No match.

Common mistakes candidates make

• One-way mapping: Only checking if pattern can be transformed into word without checking if multiple pattern characters map to the same word character (e.g., "aba" mapping to "ccc").
• Inefficient logic: Creating new strings or using complex regex when simple character-by-character comparison is $O(N)$.
• Forgetting to reset: Not clearing the maps between word checks.

Interview preparation tip

A great way to simplify isomorphism problems is to "normalize" the strings. Map the first unique character seen to 'a', the second to 'b', and so on. If the normalized versions of two strings are identical, the strings match the same pattern.