Domain 2MediumMEDIUM

Find and Replace Pattern

Iterate through each word, using two hash maps to enforce a bijective mapping between pattern and word characters.

Domain: medium•Updated: 2026-09-03
#Iteration#Hash Map#O(N*L)#O(1)

Problem Breakdown

We need to identify which words in a list share the same structural pattern as a given pattern. A match requires a bijection (one-to-one correspondence) where every character in the pattern maps uniquely to exactly one character in the word, and vice versa.

  • Inputs:
    • words: List of strings (List[str]).
    • pattern: A single string (str).
  • Outputs: A list of words from words that satisfy the bijection rule with pattern.
  • Constraints & Edge Cases:
    • All words in words have length equal to len(pattern).
    • Lengths are small (up to 20), but logic must hold for any valid string.
    • Empty lists or single-character strings need handling, though constraints imply non-empty inputs (1 <= ...).
    • The mapping is local: {a -> m} in one word does not affect the validity of another word’s match against pattern.

Intuition

A naive approach might simply check if characters at index ii are consistent (e.g., if pattern has ‘a’ and later ‘b’, they must map to different chars). However, a simple consistency check isn’t enough. We need injectivity as well: two distinct characters in the pattern cannot map to the same character in the word (e.g., “abb” vs “ccc”).

  • Brute Force: Trying all permutations of letters is O(26!)O(26!), which is computationally impossible.
  • Key Insight: We can verify a match by maintaining two mappings simultaneously during iteration: one from pattern char to word char (p_to_w) and another from word char back to pattern char (w_to_p). This ensures that if we encounter a character in the word that has already been mapped, it must map back to the same pattern character.
  • Optimal Approach: Iterate through each word once (O(L)O(L)). For every position ii, check consistency and uniqueness using hash maps (dictionaries) for constant-time lookups.

Approach

  1. Initialize an empty result list res.
  2. Loop through each word in the input words:
    • Check if lengths match (though constraints guarantee this, it’s a safety check). If not, skip.
    • Create two dictionaries: p_map and w_map.
      • p_map: Tracks mapping from pattern character to word character (pattern[i] -> word[i]).
      • w_map: Tracks reverse mapping for injectivity enforcement (word[i] -> pattern[i]).
    • Iterate through each index ii of the strings:
      • Get current characters pc (from pattern) and wc (from word).
      • If pc is not in p_map:
        • Check if wc exists as a key in w_map. If yes, it means another pattern character already maps to this word character. This violates bijection -> Mismatch.
        • Otherwise, add the mapping pair: p_map[pc] = wc, w_map[wc] = pc.
      • If pc is in p_map:
        • Check if existing value matches current wc. If not (p_map[pc] != wc) -> Mismatch.
    • If the loop completes without mismatches, add word to res.
  3. Return res.

Complexity Analysis

  • Time Complexity: O(N⋅L)O(N \cdot L), where NN is the number of words and LL is the length of each word (and pattern). We iterate through every character once per word. Dictionary operations are O(1)O(1). Since alphabet size Σ=26\Sigma = 26, space for maps is constant relative to input string content but technically bounded by min⁡(Σ,L)\min(\Sigma, L), making it effectively linear with respect to the total number of characters in words.
  • Space Complexity: O(L)O(L) or O(1)O(1). We store at most one entry per unique character. Since there are only 26 lowercase English letters (or standard ASCII), the dictionary size is bounded by a small constant, making it effectively O(Σ)O(\Sigma) space for each word check.

Solution

from typing import List

def findAndReplacePattern(words: List[str], pattern: str) -> List[str]:
    res = []
    
    # Iterate over every candidate word to compare against the pattern
    for word in words:
        if len(word) != len(pattern):
            continue
            
        p_map = {}  # Maps pattern char -> word char (consistency check)
        w_map = {}  # Maps word char -> pattern char (injectivity/bijection check)
        
        match_found = True
        
        for pc, wc in zip(pattern, word):
            if pc not in p_map:
                # New mapping required. Check injectivity first via reverse map.
                if wc in w_map:
                    match_found = False
                    break
                
                # Establish bidirectional link to ensure bijection holds
                p_map[pc] = wc
                w_map[wc] = pc
            else:
                # Mapping exists, verify it hasn't changed (consistency)
                if p_map[pc] != wc:
                    match_found = False
                    break
        
        if match_found:
            res.append(word)
            
    return res

# Example usage matching the problem description
if __name__ == "__main__":
    words = ["abc","deq","mee","aqq","dkd","ccc"]
    pattern = "abb"
    print(findAndReplacePattern(words, pattern)) 

Edge Cases Handled

  • Empty Input: The loop naturally handles an empty words list by returning an empty result.
  • Single Character Words/Patterns: Logic holds as the dictionary operations execute once without collision checks failing incorrectly.
  • Duplicate Characters in Pattern (e.g., “abb”): Ensures that if ‘b’ appears twice, it must map to the same character in word and no other pattern char maps to a different word char for that target value (w_map).
  • All Same Characters: Correctly identifies mismatches where distinct pattern chars (e.g., “abc”) are forced into identical positions or vice versa.