MediumNo. 0890
Find and Replace Pattern — LeetCode 890 Python Solution
- Pattern
- Hash Map
- Topics
- Array, Hash Table, String
- Reading time
- 2 min
- Source
- leetcode.com
The problem
Given a list of strings words and a string pattern, return a list of words[i] that match pattern. You may return the answer in any order.
Example
- Input
- words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb"
- Output
- ["mee","aqq"]
- Explanation
- "mee" matches the pattern because there is a permutation {a -> m, b -> e, ...}.
Python solution
class Solution:
def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:
def match(s, t):
m1, m2 = [0] * 128, [0] * 128
for i, (a, b) in enumerate(zip(s, t), 1):
if m1[ord(a)] != m2[ord(b)]:
return False
m1[ord(a)] = m2[ord(b)] = i
return True
return [word for word in words if match(word, pattern)]Complexity
- Time
- O(n)
- Space · auxiliary
- O(n)
Pattern: Hash Map
Trade memory for time: remember what you have seen so the second pass never happens. LeetCode 890. Find and Replace Pattern is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Hash Table.
The hash map guide has the Python template for the pattern and the 709 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0893 | Groups of Special-Equivalent Strings | Medium |
| 0049 | Group Anagrams | Medium |
| 0139 | Word Break | Medium |
| 0140 | Word Break II | Hard |
| 0336 | Palindrome Pairs | Hard |
| 0500 | Keyboard Row | Easy |
Frequently asked questions
- How hard is LeetCode 890. Find and Replace Pattern?
LeetCode 890. Find and Replace Pattern is rated Medium on LeetCode.
- What is the time complexity of LeetCode 890. Find and Replace Pattern?
The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 890. Find and Replace Pattern?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 890. Find and Replace Pattern cover?
LeetCode 890. Find and Replace Pattern is tagged Array, Hash Table and String on LeetCode.