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
wordsthat satisfy the bijection rule withpattern. - Constraints & Edge Cases:
- All words in
wordshave length equal tolen(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 againstpattern.
- All words in
Intuition
A naive approach might simply check if characters at index 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 , which is computationally impossible.
- Key Insight: We can verify a match by maintaining two mappings simultaneously during iteration: one from
patternchar towordchar (p_to_w) and another fromwordchar back topatternchar (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 (). For every position , check consistency and uniqueness using hash maps (dictionaries) for constant-time lookups.
Approach
- Initialize an empty result list
res. - Loop through each
wordin the inputwords:- Check if lengths match (though constraints guarantee this, it’s a safety check). If not, skip.
- Create two dictionaries:
p_mapandw_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 of the strings:
- Get current characters
pc(from pattern) andwc(from word). - If
pcis not inp_map:- Check if
wcexists as a key inw_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.
- Check if
- If
pcis inp_map:- Check if existing value matches current
wc. If not (p_map[pc] != wc) -> Mismatch.
- Check if existing value matches current
- Get current characters
- If the loop completes without mismatches, add
wordtores.
- Return
res.
Complexity Analysis
- Time Complexity: , where is the number of words and is the length of each word (and pattern). We iterate through every character once per word. Dictionary operations are . Since alphabet size , space for maps is constant relative to input string content but technically bounded by , making it effectively linear with respect to the total number of characters in
words. - Space Complexity: or . 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 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
wordslist 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
wordand 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.