Hex.*

LC890 - Find and Replace Pattern

Posted on In
Leetcode: 126/2658 (52+60+14)

Description

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.

A word matches the pattern if there exists a permutation of letters p so that after replacing every letter x in the pattern with p(x), we get the desired word.

Recall that a permutation of letters is a bijection from letters to letters: every letter maps to another letter, and no two letters map to the same letter.

Example 1:

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, …}.
“ccc” does not match the pattern because {a -> c, b -> c, …} is not a permutation, since a and b map to the same letter.
Example 2:

Input: words = [“a”,”b”,”c”], pattern = “a”
Output: [“a”,”b”,”c”]

Constraints:

1 <= pattern.length <= 20
1 <= words.length <= 50
words[i].length == pattern.length
pattern and words[i] are lowercase English letters.

Solution

According to the topic of the use rule, traverse each word, check all the words existing in each word one by one, and determine whether the mapping is satisfied.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# O(nm) time | O(n) space
class Solution:
    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:
        res = []
        for word in words:
            dic_pattern = {}
            dic_words = {}
            
            for i in range(len(word)):
                if pattern[i] not in dic_pattern:
                    dic_pattern[pattern[i]] = word[i]
                else:
                    if dic_pattern[pattern[i]] != word[i]:
                        break
                
                if word[i] not in dic_words:
                    dic_words[word[i]] = pattern[i]
                else:
                    if dic_words[word[i]] != pattern[i]:
                        break
                
                if i == len(word)-1:
                    res.append(word)
        return res