Find and Replace Pattern — LeetCode 890 Python Solution

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

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