856. 句子相似性

中文English

给出两个句子words1和words2（每个用一个字符串数组表示），和一个相似词对数组pairs，你需要判断两个句子是否相似。

例如，如果相似词对是pairs = [["great", "fine"], ["acting","drama"], ["skills","talent"]]，那么words1 = great acting skills和words2 = fine drama talent是相似的。

需要注意，相似关系是不可传递的。例如，如果"great"和"fine"相似，"fine"和"good"相似，"great"和"good"不是一定相似的。

然而，相似性是对称的。例如，"great"和"fine"相似，则"fine"和"great"也是相似的，这两者是等价的。

另外，一个单词永远与它本身相似。例如，句子words1 = ["great"], words2 = ["great"], pairs = []是相似的，尽管没有相似词对。

最后，两个句子只有在单词数相等的情况下才可能相似。所以，句子words1 = ["great"]永远不可能与句子words2 = ["doubleplus","good"]相似。

样例

样例1

输入: words1 = ["great","acting","skills"], words2 = ["fine","drama","talent"] and pairs = [["great","fine"],["drama","acting"],["skills","talent"]]
输出: true
解释:
"great"和"fine"相似
"acting"和"drama"相似
"skills"和"talent"相似

样例2

输入: words1 = ["fine","skills","acting"], words2 = ["fine","drama","talent"] and pairs = [["great","fine"],["drama","acting"],["skills","talent"]]
输出: false
解释:
"fine"和"fine"相同
"skills"和"drama"不相似
"acting"和"talent"不相似

注意事项

1. words1和words2的长度不会超过1000。
2. pairs的长度不会超过2000。
3. 每一个pairs[i]的长度是2。
4. 每一个words[i]和pairs[i][j]的长度在[1, 20]范围内。

class Solution:
    """
    @param words1: a list of string
    @param words2: a list of string
    @param pairs: a list of string pairs
    @return: return a boolean, denote whether two sentences are similar or not
    """
    def isSentenceSimilarity(self, words1, words2, pairs):
        # write your code here
        len1, len2 = len(words1), len(words2)
        if len1 != len2: return False
        
        #生成字典
        pairs_dict = {}
        for pair in pairs:
            if pair[0] not in pairs_dict:
                pairs_dict[pair[0]] = [pair[1]]
            else:
                pairs_dict[pair[0]].append(pair[1])
                
            if pair[1] not in pairs_dict:
                pairs_dict[pair[1]] = [pair[0]]
            else:
                pairs_dict[pair[1]].append(pair[0])
        
        #判断
        for i in range(len1):
            if words1[i] == words2[i]:
                continue
            if words2[i] in pairs_dict[words1[i]]:
                continue
            if words1[i] in pairs_dict[words2[i]]:
                continue
            return False
            
        return True