LeetCode每日一题——890. 查找和替换模式

题目

你有一个单词列表 words 和一个模式 pattern，你想知道 words 中的哪些单词与模式匹配。

如果存在字母的排列 p ，使得将模式中的每个字母 x 替换为 p(x) 之后，我们就得到了所需的单词，那么单词与模式是匹配的。

（回想一下，字母的排列是从字母到字母的双射：每个字母映射到另一个字母，没有两个字母映射到同一个字母。）

返回 words 中与给定模式匹配的单词列表。

你可以按任何顺序返回答案。

示例

输入：words = [“abc”,“deq”,“mee”,“aqq”,“dkd”,“ccc”], pattern = “abb”
输出：[“mee”,“aqq”]
解释： “mee” 与模式匹配，因为存在排列 {a -> m, b -> e, …}。 "ccc"与模式不匹配，因为 {a -> c, b -> c, …} 不是排列。 因为 a 和 b 映射到同一个字母。

提示：

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

思路

本题考串的模式匹配问题，本题的具体要求是要从给定的字符串列表words中找出形式和给定字符串pattern格式相同的字符串集合，如pattern = ‘abc’， 从words中找到的与之相匹配的字符串也必须是三个字符各不相同的字符串如’bac’,‘xyz’等，又比如pattern = ‘aba’， 从words中找到的与之相匹配的字符串也必须是相同位置相等的字符串如’xyx’,'bab’等。因为题中所给words中字符都和pattern等长，所以具体解题可分为两种情况：

1. 给定pattern长度为1，words中的字符都和pattern模式相同，直接返回words
2. 给定pattern长度大于1，首先遍历pattern将其格式记录于哈希表里（从第二位开始向前面的每一位比较，生成一个布尔数组，放在哈希表里待使用），然后遍历words中的每个字符串，使用和上面同样的方法从第二位开始向前面的每一位比较，生成一个布尔数组，然后和哈希表中的数组结果相比较，如果全部相等则为答案。

题解

def findAndReplacePattern(words: List[str], pattern: str) -> List[str]:
	# 情况1
    if len(pattern) == 1:
        return words
    # 情况2
    # 哈希表
    temp = {
    }
    res = []
    for i in range(1, len(pattern)):
        ans = []
        # 每一位朝前比较
        for j in range(1, i+1):
            if pattern[i] == pattern[i-j]:
                ans.append(True)
            else:
                ans.append(False)
        # 每一位朝前比较的布尔数组存于哈希表中
        temp[i] = ans
    for i in words:
    	# index记录当前比较的字符串中布尔数组和哈希表中布尔数组相同的个数
        index = 0
        for j in range(1, len(i)):
            use = []
            # 同样的方法每一位朝前比较
            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 index == len(i) - 1:
            res.append(i)
    return res