Problem Description

You are given a list of strings words and a string pattern. Your task is to find all words from the list that match the given pattern.

A word matches the pattern if you can create a one-to-one character mapping (bijection) between the pattern and the word. This means:

• Each character in the pattern maps to exactly one character in the word
• Each character in the word maps to exactly one character in the pattern
• The mapping must be consistent throughout the entire string

For example:

• If pattern = "abb" and word = "egg", they match because we can map a → e and b → g
• If pattern = "abb" and word = "abc", they don't match because b would need to map to both b and c

The solution uses two arrays m1 and m2 to track when each character was first encountered. For matching strings, characters at the same positions should have been first encountered at the same index. The algorithm iterates through both strings simultaneously:

• m1[ord(a)] stores the position where character a from the word was first seen
• m2[ord(b)] stores the position where character b from the pattern was first seen
• If these values differ at any position, the strings don't match

The function returns all words that successfully match the pattern, in any order.

Intuition

The key insight is that two strings follow the same pattern if their characters appear in the same relative positions. Rather than building an explicit character-to-character mapping, we can check if the pattern of first occurrences is identical.

Think about it this way: when we scan through "abb" and "egg" character by character:

• At position 0: 'a' appears for the first time, 'e' appears for the first time
• At position 1: 'b' appears for the first time, 'g' appears for the first time
• At position 2: 'b' appears again (was first seen at position 1), 'g' appears again (was first seen at position 1)

The pattern of first appearances matches perfectly! This is the core idea - instead of tracking "a maps to e, b maps to g", we track "when did each character first appear?"

We can implement this by maintaining two arrays that record the first occurrence position of each character. As we traverse both strings simultaneously:

• If a character in the word was first seen at position i, and the corresponding character in the pattern was first seen at position j, then i must equal j for a valid match
• If they differ, the strings don't follow the same pattern

This approach elegantly handles the bijection requirement automatically. If two different characters in the pattern try to map to the same character in the word (or vice versa), their first occurrence positions will be different, causing the match to fail.

The beauty of this solution is that it transforms a seemingly complex mapping problem into a simple comparison of occurrence patterns, making the code both efficient and easy to understand.

Solution Approach

The implementation uses a helper function match(s, t) to check if a word s matches the pattern t.

Data Structures:

• Two arrays m1 and m2 of size 128 (to cover all ASCII characters)
• m1 tracks first occurrence positions for characters in the word
• m2 tracks first occurrence positions for characters in the pattern

Algorithm Steps:

1. Initialize tracking arrays: Create m1 and m2 with all zeros. A zero value means the character hasn't been seen yet.

2. Simultaneous traversal: Use enumerate(zip(s, t), 1) to iterate through both strings together, starting the index from 1 (to distinguish from the initial 0 values).

3. Character position checking: For each pair of characters (a, b) at position i:

   • Convert characters to ASCII values using ord(a) and ord(b)
   • Check if m1[ord(a)] != m2[ord(b)]
   • If they differ, it means:
     • Either one character was seen before and the other wasn't
     • Or both were seen before but at different positions
   • In either case, return False as the pattern doesn't match

4. Update first occurrence: If the positions match (both are 0 or both have the same value), update both to the current position i:

   m1[ord(a)] = m2[ord(b)] = i

5. Filter the words: Use a list comprehension to filter all words that match the pattern:

   return [word for word in words if match(word, pattern)]

Why this works:

• When both arrays have 0 at a position, both characters are appearing for the first time
• When both arrays have the same non-zero value, both characters appeared before at the same position
• Any mismatch in these values indicates the bijection property is violated

Time Complexity: O(n * m) where n is the number of words and m is the length of each word/pattern Space Complexity: O(1) for the tracking arrays (fixed size 128)

Example Walkthrough

Let's walk through finding words that match the pattern "abb" from the list ["egg", "abc", "foo"].

Checking "egg" against pattern "abb":

Initialize m1 and m2 arrays (all zeros). We'll track only relevant positions for clarity:

Result: "egg" matches! The pattern holds because 'a'→'e' and 'b'→'g' consistently.

Checking "abc" against pattern "abb":

Reset m1 and m2 arrays:

Result: "abc" doesn't match! The second 'b' in pattern should map to the same character as the first 'b', but here it maps to 'c' instead of 'b'.

Checking "foo" against pattern "abb":

Reset m1 and m2 arrays:

Result: "foo" matches! The pattern holds because 'a'→'f' and 'b'→'o' consistently.

Final output: ["egg", "foo"]

The algorithm elegantly detects pattern mismatches by comparing when characters were first encountered. If the "first seen" positions don't align, the bijection is broken.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n * m) where n is the number of words in the input list and m is the length of each word/pattern.

• The outer loop iterates through all n words in the list
• For each word, the match function is called which:
  • Iterates through m characters (using zip and enumerate)
  • Each iteration performs constant time operations: array lookups O(1) and assignments O(1)
• Therefore, the total time complexity is O(n * m)

Space Complexity: O(1) for the auxiliary space (excluding the output list).

• The match function creates two fixed-size arrays m1 and m2, each of size 128 (for ASCII characters)
• These arrays have constant size regardless of input size, contributing O(1) space
• The list comprehension creates an output list that could contain up to n words in the worst case, which would be O(n * m) for the output
• However, considering only auxiliary space used by the algorithm itself (not including the output), the space complexity is O(1)

If we include the output space, the total space complexity would be O(n * m) in the worst case where all words match the pattern.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Handling of Different Length Strings

One common pitfall is assuming that the word and pattern will always have the same length. If they don't, the zip() function will silently truncate to the shorter length, potentially causing false positives.

Problem Example:

• Pattern: "ab"
• Word: "abc"
• The zip would only check "ab" vs "ab" and miss the extra "c"

Solution: Add a length check before processing:

def matches_pattern(word: str, pattern: str) -> bool:
    if len(word) != len(pattern):
        return False
    # ... rest of the code

2. Using Dictionary Instead of Array for Character Mapping

While using a dictionary seems more intuitive, it can lead to subtle bugs if not handled carefully:

Problematic approach:

def matches_pattern(word: str, pattern: str) -> bool:
    word_to_pattern = {}
    pattern_to_word = {}
  
    for w, p in zip(word, pattern):
        if w in word_to_pattern:
            if word_to_pattern[w] != p:
                return False
        else:
            word_to_pattern[w] = p
      
        # Bug: Forgetting to check reverse mapping
    return True

This only checks one direction of the bijection and would incorrectly accept cases where multiple word characters map to the same pattern character.

Correct dictionary approach:

def matches_pattern(word: str, pattern: str) -> bool:
    if len(word) != len(pattern):
        return False
  
    word_to_pattern = {}
    pattern_to_word = {}
  
    for w, p in zip(word, pattern):
        if w in word_to_pattern:
            if word_to_pattern[w] != p:
                return False
        else:
            word_to_pattern[w] = p
      
        if p in pattern_to_word:
            if pattern_to_word[p] != w:
                return False
        else:
            pattern_to_word[p] = w
  
    return True

3. Starting Index from 0 Instead of 1

If you start the enumerate index from 0, the initial array values (also 0) would be indistinguishable from "character seen at position 0", causing incorrect pattern matching:

Problematic code:

for index, (word_char, pattern_char) in enumerate(zip(word, pattern)):  # Starts from 0
    word_char_ascii = ord(word_char)
    pattern_char_ascii = ord(pattern_char)
  
    # Bug: Can't distinguish between "not seen" and "seen at position 0"
    if word_last_seen[word_char_ascii] != pattern_last_seen[pattern_char_ascii]:
        return False

Example where this fails:

• Pattern: "aa"
• Word: "bb"
• At index 0: Both arrays are 0 (initial value), so we set them to 0
• At index 1: Both arrays are still 0 (we set them to 0 in previous step), condition passes incorrectly

Solution: Always use enumerate(zip(word, pattern), start=1) to avoid this ambiguity.

4. Array Size Assumptions

Using an array of size 128 assumes only ASCII characters. If the input contains Unicode characters beyond ASCII range, this will cause an IndexError:

Solution for Unicode support:

def matches_pattern(word: str, pattern: str) -> bool:
    if len(word) != len(pattern):
        return False
  
    word_mapping = {}
    pattern_mapping = {}
  
    for index, (w, p) in enumerate(zip(word, pattern), start=1):
        word_last = word_mapping.get(w, 0)
        pattern_last = pattern_mapping.get(p, 0)
      
        if word_last != pattern_last:
            return False
      
        word_mapping[w] = index
        pattern_mapping[p] = index
  
    return True