Leetcode daily question - 890 Find and replace mode

subject

You have a list of words words And a pattern pattern, Do you want to know words Which words in match the pattern .

If there is an arrangement of letters p , Make every letter in the pattern x Replace with p(x) after , We get the words we need , So the words match the patterns .

（ Think about it , The arrangement of letters is from letter to letter ： Each letter maps to another letter , No two letters map to the same letter .）

return words List of words matching the given pattern in .

You can return the answers in any order .

Example

Input ：words = [“abc”,“deq”,“mee”,“aqq”,“dkd”,“ccc”], pattern = “abb”
Output ：[“mee”,“aqq”]
explain ： “mee” Match pattern , Because there are permutations {a -> m, b -> e, …}. "ccc" Does not match pattern , because {a -> c, b -> c, …} It's not a permutation . because a and b Map to the same letter .

Tips ：

1 <= words.length <= 50
1 <= pattern.length = words[i].length <= 20

Ideas

The pattern matching problem of the test string of this question , The specific requirement of this question is to list the given strings words Find the form and given string in pattern A collection of strings in the same format , Such as pattern = ‘abc’, from words The matching string found in must also be a string with three different characters, such as ’bac’,‘xyz’ etc. , And such as pattern = ‘aba’, from words The matching string found in must also be a string with the same position, such as ’xyx’,'bab’ etc. . Because the question gives words Both Chinese characters and pattern Equal length , So the specific problem-solving can be divided into two cases ：

1. Given pattern The length is 1,words The characters in are all the same as pattern Same pattern , Go straight back to words
2. Given pattern Longer than 1, First traverse pattern Record the format in the hash table （ Start from the second place and compare with each one in front , Generate a Boolean array , Put it in the hash table for use ）, Then traverse words Each string in , Use the same method as above to compare from the second bit to each of the previous bits , Generate a Boolean array , Then compare with the array result in the hash table , If all are equal, it is the answer .

Answer key

def findAndReplacePattern(words: List[str], pattern: str) -> List[str]:
	#  situation 1
    if len(pattern) == 1:
        return words
    #  situation 2
    #  Hashtable 
    temp = {
    }
    res = []
    for i in range(1, len(pattern)):
        ans = []
        #  Each one of them looks forward and compares 
        for j in range(1, i+1):
            if pattern[i] == pattern[i-j]:
                ans.append(True)
            else:
                ans.append(False)
        #  The Boolean array for each bit forward comparison is stored in the hash table 
        temp[i] = ans
    for i in words:
    	# index Record the same number of Boolean arrays in the currently compared string and the hash table 
        index = 0
        for j in range(1, len(i)):
            use = []
            #  In the same way, each one of them looks forward 
            for k in range(1, j+1):
                if i[j] == i[j-k]:
                    use.append(True)
                else:
                    use.append(False)
            if use == temp[j]:
                index += 1
        #  If the Boolean array and the hash table are all equal , Add answers 
        if index == len(i) - 1:
            res.append(i)
    return res