Difficulty: 🟡 Medium
Topics: Array, Hash Table, String

Solution

Problem Understanding

The problem gives us a list of words and a target pattern string. We need to determine which words follow the exact same structural character relationship as the pattern.

A word matches the pattern if there exists a one to one mapping between characters in the pattern and characters in the word. This mapping must be a bijection, which means:

Each pattern character maps to exactly one word character
No two different pattern characters map to the same word character

The actual letters do not matter. What matters is whether the repetition structure is identical.

For example, consider the pattern "abb":

The first character 'a' appears once
The second and third characters are both 'b'

So any matching word must have:

One unique character at index 0
Another character repeated at indices 1 and 2

The word "mee" matches because:

'a' -> 'm'
'b' -> 'e'

This preserves the structure.

The word "ccc" does not match because:

'a' -> 'c'
'b' -> 'c'

Now two different pattern characters map to the same word character, which violates the bijection requirement.

The input constraints are small:

pattern.length <= 20
words.length <= 50

This tells us that even relatively straightforward checking solutions will run comfortably within limits. We do not need advanced optimization techniques. A clean hash map based solution is ideal.

The problem also guarantees:

Every word has the same length as the pattern
All characters are lowercase English letters

This removes the need for length validation during matching.

Some important edge cases include:

Multiple pattern characters mapping to the same word character
A single pattern character mapping inconsistently
Single character patterns
Words with all repeated characters
Patterns where every character is unique

A naive implementation that only checks one direction of mapping can fail on these cases.

Approaches

Brute Force Approach

The brute force idea is to try constructing every possible mapping between pattern characters and word characters for each word.

For every word, we compare characters position by position and maintain all possible substitutions. At each step, we verify whether the current mapping remains consistent.

To correctly validate a bijection, we must check:

A pattern character always maps to the same word character
A word character is not already assigned to another pattern character

This approach is already workable because the constraints are small. However, if implemented carelessly using repeated searches or reconstruction of mappings, it can become unnecessarily inefficient.

The brute force method is conceptually simple, but it does extra work because it repeatedly validates character relationships from scratch.

Optimal Approach

The key insight is that pattern matching depends entirely on preserving character relationships.

We can efficiently verify this by maintaining two hash maps:

pattern_to_word
word_to_pattern

As we scan characters from left to right:

If a mapping already exists, it must remain consistent
If no mapping exists yet, we create it
If either direction conflicts, the word does not match

Using two maps guarantees a true bijection.

This solution is efficient because every character is processed exactly once for each word.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(W × N²)	O(N)	Repeatedly validates mappings with extra checking
Optimal	O(W × N)	O(N)	Uses two hash maps for direct bijection validation

Where:

W = number of words
N = length of each word and pattern

Algorithm Walkthrough

Initialize an empty result list.

This list will store all words that successfully match the pattern. 2. For each word in words, check whether it matches the pattern.

Since every word has the same length as the pattern, we can directly compare characters index by index. 3. Create two hash maps.

The first map stores:

pattern character -> word character

The second map stores:

word character -> pattern character

We need both maps because bijection works in both directions. 4. Iterate through each character position.

At index i:

Let p = pattern[i]
Let w = word[i]

Check whether p already has a mapping.

If it does:

The mapped character must equal w

Otherwise:

Create a new mapping p -> w

Check whether w already has a reverse mapping.

If it does:

The mapped pattern character must equal p

Otherwise:

Create a new reverse mapping w -> p

If either consistency check fails, stop processing this word.

The word cannot match the pattern. 8. If the entire word is processed successfully, append it to the result list. 9. Return the result list after processing all words.

Why it works

The algorithm maintains a strict one to one correspondence between pattern characters and word characters throughout the scan.

At every position:

A pattern character can only map to one word character
A word character can only map to one pattern character

Because both directions are validated simultaneously, the mapping is guaranteed to be bijective. Therefore, any accepted word preserves the exact structural pattern relationship.

Python Solution

from typing import List

class Solution:
    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:
        def matches(word: str) -> bool:
            pattern_to_word = {}
            word_to_pattern = {}

            for p_char, w_char in zip(pattern, word):
                if p_char in pattern_to_word:
                    if pattern_to_word[p_char] != w_char:
                        return False
                else:
                    pattern_to_word[p_char] = w_char

                if w_char in word_to_pattern:
                    if word_to_pattern[w_char] != p_char:
                        return False
                else:
                    word_to_pattern[w_char] = p_char

            return True

        result = []

        for word in words:
            if matches(word):
                result.append(word)

        return result

The solution defines a helper function matches() that determines whether a single word follows the same structure as the pattern.

Inside this helper:

pattern_to_word tracks mappings from pattern characters to word characters
word_to_pattern tracks reverse mappings

The algorithm iterates through corresponding characters using zip(pattern, word).

For each pair:

If the mapping already exists, it must remain consistent
Otherwise, the mapping is created

The reverse direction is checked the same way.

If any inconsistency appears, the function immediately returns False.

If the entire word is processed without conflicts, the word matches the pattern and returns True.

The main function simply applies this validation to every word and collects the valid matches.

Go Solution

func findAndReplacePattern(words []string, pattern string) []string {
    matches := func(word string) bool {
        patternToWord := make(map[byte]byte)
        wordToPattern := make(map[byte]byte)

        for i := 0; i < len(pattern); i++ {
            pChar := pattern[i]
            wChar := word[i]

            if mappedChar, exists := patternToWord[pChar]; exists {
                if mappedChar != wChar {
                    return false
                }
            } else {
                patternToWord[pChar] = wChar
            }

            if mappedChar, exists := wordToPattern[wChar]; exists {
                if mappedChar != pChar {
                    return false
                }
            } else {
                wordToPattern[wChar] = pChar
            }
        }

        return true
    }

    result := []string{}

    for _, word := range words {
        if matches(word) {
            result = append(result, word)
        }
    }

    return result
}

The Go implementation follows the exact same logic as the Python solution.

A few Go specific details are worth noting:

Go strings are indexed as bytes because the input only contains lowercase English letters
map[byte]byte is used for character mappings
The helper function is implemented as an inline closure
The result slice starts empty and grows using append

Since the problem only uses ASCII lowercase letters, byte indexing is completely safe and efficient.

Worked Examples

Example 1

Input:

words = ["abc","deq","mee","aqq","dkd","ccc"]
pattern = "abb"

We process each word independently.

Word: `"abc"`

Index	Pattern Char	Word Char	pattern_to_word	word_to_pattern	Valid
0	a	a	{a:a}	{a:a}	Yes
1	b	b	{a:a,b:b}	{a:a,b:b}	Yes
2	b	c	conflict	conflict	No

At index 2, 'b' was previously mapped to 'b', but now tries mapping to 'c'.

This word fails.

Word: `"deq"`

Index	Pattern Char	Word Char	pattern_to_word	word_to_pattern	Valid
0	a	d	{a:d}	{d:a}	Yes
1	b	e	{a:d,b:e}	{d:a,e:b}	Yes
2	b	q	conflict	conflict	No

This word fails because 'b' maps inconsistently.

Word: `"mee"`

Index	Pattern Char	Word Char	pattern_to_word	word_to_pattern	Valid
0	a	m	{a:m}	{m:a}	Yes
1	b	e	{a:m,b:e}	{m:a,e:b}	Yes
2	b	e	unchanged	unchanged	Yes

This word matches.

Word: `"aqq"`

Index	Pattern Char	Word Char	pattern_to_word	word_to_pattern	Valid
0	a	a	{a:a}	{a:a}	Yes
1	b	q	{a:a,b:q}	{a:a,q:b}	Yes
2	b	q	unchanged	unchanged	Yes

This word matches.

Word: `"dkd"`

Index	Pattern Char	Word Char	pattern_to_word	word_to_pattern	Valid
0	a	d	{a:d}	{d:a}	Yes
1	b	k	{a:d,b:k}	{d:a,k:b}	Yes
2	b	d	conflict	conflict	No

This word fails because 'b' cannot map to both 'k' and 'd'.

Word: `"ccc"`

Index	Pattern Char	Word Char	pattern_to_word	word_to_pattern	Valid
0	a	c	{a:c}	{c:a}	Yes
1	b	c	conflict	conflict	No

This word fails because two pattern characters map to the same word character.

Final output:

["mee", "aqq"]

Example 2

Input:

words = ["a","b","c"]
pattern = "a"

Each word has length 1.

For every word:

Index	Pattern Char	Word Char	Valid
0	a	current char	Yes

Since there is only one character, every mapping is valid.

Final output:

["a", "b", "c"]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(W × N)	Each character of each word is processed once
Space	O(N)	Hash maps store at most one entry per unique character

Where:

W is the number of words
N is the pattern length

The algorithm scans every word exactly once. For each word, it performs constant time hash map operations for every character position.

The auxiliary space comes from the two hash maps. In the worst case, every character is unique, so the maps store up to N entries.

Test Cases

solution = Solution()

# Provided example 1
assert sorted(solution.findAndReplacePattern(
    ["abc", "deq", "mee", "aqq", "dkd", "ccc"],
    "abb"
)) == ["aqq", "mee"]  # standard matching case

# Provided example 2
assert sorted(solution.findAndReplacePattern(
    ["a", "b", "c"],
    "a"
)) == ["a", "b", "c"]  # single character pattern

# All characters unique
assert sorted(solution.findAndReplacePattern(
    ["abc", "xyz", "foo"],
    "abc"
)) == ["abc", "xyz"]  # repeated letters should fail

# All characters repeated
assert sorted(solution.findAndReplacePattern(
    ["aaa", "bbb", "aba", "ccc"],
    "ddd"
)) == ["aaa", "bbb", "ccc"]  # every char must map consistently

# Reverse mapping conflict
assert solution.findAndReplacePattern(
    ["ccc"],
    "abb"
) == []  # two pattern chars cannot map to same letter

# Mixed valid and invalid
assert sorted(solution.findAndReplacePattern(
    ["mnn", "abb", "xyz", "xyy"],
    "foo"
)) == ["abb", "mnn", "xyy"]  # repeated structure required

# Pattern with alternating characters
assert sorted(solution.findAndReplacePattern(
    ["abab", "xyxy", "aaaa", "abca"],
    "baba"
)) == ["abab", "xyxy"]  # alternating structure

# No matches
assert solution.findAndReplacePattern(
    ["abc", "def", "ghi"],
    "aab"
) == []  # no repeated pattern structure

# Single word valid
assert solution.findAndReplacePattern(
    ["mee"],
    "abb"
) == ["mee"]  # single valid word

# Single word invalid
assert solution.findAndReplacePattern(
    ["abc"],
    "abb"
) == []  # single invalid word

Test Summary

Test	Why
`["abc","deq","mee","aqq","dkd","ccc"]`	Validates standard matching behavior
`["a","b","c"]`	Tests single character patterns
Unique character pattern	Ensures repeated letters fail correctly
Repeated character pattern	Validates consistent repeated mappings
`"ccc"` vs `"abb"`	Tests reverse bijection conflicts
Mixed valid and invalid words	Ensures filtering works correctly
Alternating patterns	Verifies nontrivial repetition structure
No matches	Confirms empty result handling
Single valid word	Tests minimal successful input
Single invalid word	Tests minimal failing input

Edge Cases

Multiple Pattern Characters Mapping to the Same Word Character

A common mistake is checking only whether a pattern character maps consistently, while ignoring whether two different pattern characters map to the same word character.

For example:

pattern = "abb"
word = "ccc"

A one directional map would incorrectly allow:

a -> c
b -> c

This violates the bijection rule because two pattern characters map to the same character.

The implementation avoids this bug by maintaining the reverse map word_to_pattern.

One Pattern Character Mapping Inconsistently

Another important edge case occurs when a pattern character maps to different characters later in the word.

Example:

pattern = "abb"
word = "abc"

Initially:

b -> b

Later:

b -> c

This breaks consistency.

The implementation checks existing mappings before assigning new ones, so inconsistencies are detected immediately.

Single Character Inputs

When the pattern length is 1, every single character word should match.