0890._Find_and_Replace_Pattern.md

890. Find and Replace Pattern

难度: Medium

刷题内容

原题连接

• https://leetcode.com/problems/find-and-replace-pattern/description/

内容描述

You have a list of words and a pattern, and you want to know which words in words matches the pattern.

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.)

Return a list of the words in words that match the given pattern. 

You may return the answer in any order.

 

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.
 

Note:

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

解题方案

思路 1 - 时间复杂度: O(Nk)- 空间复杂度: O(k)***** 这里k为最长的那个字符串的长度

1. 定义一个convert函数

• 首先对于传进来的word做一个for loop
• 只要字符没有出现过就用一个全新的num来对应它
• 否则就用之前存在dict里面的它所对应num来对应它

2. 比较每个word convert之后是否于pattern convert之后相等，相等就加入最终结果
3. 返回最终结果

class Solution(object):
    def findAndReplacePattern(self, words, pattern):
        """
        :type words: List[str]
        :type pattern: str
        :rtype: List[str]
        """
        def convert(word):
            lookup = {}
            num = 0
            word_convert = ''
            for i in word:
                if i not in lookup:                # 第一次出现这个字符
                    num += 1                       # 用一个全新的num来对应它
                    word_convert += str(num)       
                    lookup[i] = num                # 存进dict供给后面用
                else:
                    word_convert += str(lookup[i]) # 之前出现过了这个字符那么就加上它之前对应的数字
            return word_convert
        pattern_convert = convert(pattern)
        res = []
        for word in words:
            if convert(word) == pattern_convert:
                res.append(word)
        return res