查找和替换模式

难度: Medium

你有一个单词列表 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

Submission

运行时间: 20 ms

内存: 0.0 MB

class Solution:
    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:
        
        def mapTo(word:str,pattern:str)->bool:
            if word==pattern:
                return True
            dp1={}
            dp2={}
            
            for i in range(len(word)):
                w=word[i]
                p=pattern[i]
                
                if w in dp1:
                    if p!=dp1[w]:
                        return False
                    if p not in dp2:
                        return False
                    else:
                        if w!=dp2[p]:
                            return False
                else:
                    if p in dp2:
                        return False
                    else:
                        dp1[w]=p
                        dp2[p]=w
            return True
        
        ans=[]
        for word in words:
            if mapTo(word,pattern):
                ans.append(word)
        return ans

Explain

该题解的思路是利用两个哈希表 dp1 和 dp2 来记录单词和模式之间的映射关系。遍历单词和模式的每个字符，对于当前的字符 w 和 p，如果 w 已经在 dp1 中出现过，则判断 p 是否等于 dp1[w]，如果不相等则说明不满足双射关系，返回 False。同时还需判断 p 是否在 dp2 中出现，如果 p 不在 dp2 中，说明存在两个字母映射到同一个字母的情况，返回 False。如果 p 在 dp2 中，则判断 w 是否等于 dp2[p]，如果不相等则返回 False。如果 w 不在 dp1 中，则判断 p 是否在 dp2 中，如果在则返回 False，否则将 w 和 p 的映射关系分别加入 dp1 和 dp2 中。最后遍历完整个单词和模式，如果满足双射关系则返回 True，否则返回 False。对于每个单词都调用 mapTo 函数进行判断，将满足条件的单词加入结果列表中返回。

时间复杂度: O(n*m)

空间复杂度: O(n+m)

class Solution:
    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:
        
        def mapTo(word:str,pattern:str)->bool:
            if word==pattern:
                return True
            dp1={}  # 记录单词到模式的映射
            dp2={}  # 记录模式到单词的映射
            
            for i in range(len(word)):
                w=word[i]
                p=pattern[i]
                
                if w in dp1:
                    if p!=dp1[w]:  # 判断是否满足双射关系
                        return False
                    if p not in dp2:
                        return False
                    else:
                        if w!=dp2[p]:
                            return False
                else:
                    if p in dp2:  # 判断是否存在两个字母映射到同一个字母的情况
                        return False
                    else:
                        dp1[w]=p  # 记录映射关系
                        dp2[p]=w
            return True
        
        ans=[]
        for word in words:
            if mapTo(word,pattern):  # 对每个单词调用 mapTo 函数进行判断
                ans.append(word)
        return ans

Explore

在哈希表dp1中找到w后还需要检查p是否不在dp2中，是为了确保模式字符串p到单词字符串w的映射也是一一对应的。如果在dp1中找到了w，说明我们已经为w定义了一个映射目标p，此时如果p不在dp2中，或者p在dp2中但映射的不是w，那么就破坏了一一对应的关系。这种情况可能在输入中有重复字符的单词或模式字符串时发生，例如单词'abba'和模式'noon'，在遍历到最后一个字符时，'a'和'n'应该形成映射，但如果之前的映射已经建立且不一致，则会有问题。

在解题思路中，遇到没有映射关系的字符时，需要同时更新dp1和dp2两个哈希表以保持这两个映射的一致性和完整性。dp1记录单词到模式的映射，而dp2记录模式到单词的映射。如果只更新一个哈希表，将无法确保另一个方向的映射正确，这可能导致后续字符映射检查时出现错误。更新两个表确保了无论从单词到模式还是从模式到单词的映射都是正确和一致的。

代码中对于`if w in dp1`和`if p in dp2`的处理逻辑基本上是对称的，但在实际应用中可能略显不对称。这是因为这两个条件各自验证的是从单词到模式和从模式到单词的映射关系。尽管逻辑上这两个条件应该对称，但在具体实现时，它们的检查顺序和映射的更新时机可能略有不同，这主要取决于代码编写者的逻辑组织方式。

在判断`if p!=dp1[w]`时，确实不需要额外判断`w!=dp2[p]`，因为这两个条件在逻辑上是等价的。如果`p!=dp1[w]`成立，意味着已经存在一个不一致的映射关系，即当前的模式字符p已经被映射到一个与当前单词字符w不同的字符。由于映射是双向一致的，这自然意味着`w!=dp2[p]`也会成立。因此，只需要检查其中一个条件即可确认映射关系是否破坏。