734.句子相似性.md

734.句子相似性

https://leetcode-cn.com/problems/sentence-similarity/solution/734ju-zi-xiang-si-xing-pythonha-xi-ji-he-zdaq/

难度：简单

题目：

给定两个句子 words1, words2 （每个用字符串数组表示），和一个相似单词对的列表 pairs ，判断是否两个句子是相似的。

例如，当相似单词对是 pairs = [["great", "fine"], ["acting","drama"], ["skills","talent"]]的时候，"great acting skills" 和 "fine drama talent" 是相似的。

注意相似关系是不具有传递性的。例如，如果 "great" 和 "fine" 是相似的，"fine" 和 "good" 是相似的，但是 "great" 和 "good" 未必是相似的。

但是，相似关系是具有对称性的。例如，"great" 和 "fine" 是相似的相当于 "fine" 和 "great" 是相似的。

而且，一个单词总是与其自身相似。例如，句子 words1 = ["great"], words2 = ["great"], pairs = [] 是相似的，尽管没有输入特定的相似单词对。

最后，句子只会在具有相同单词个数的前提下才会相似。所以一个句子 words1 = ["great"] 永远不可能和句子 words2 = ["doubleplus","good"] 相似。 注：

words1 and words2 的长度不会超过 1000。 pairs 的长度不会超过 2000。 每个pairs[i] 的长度为 2。 每个 words[i] 和 pairs[i][j] 的长度范围为 [1, 20]。

分析

语文题实锤了，文字描述太多，光题读了好几遍。重新叙述下：

1. words1，words2 是两个字符串列表
2. pairs是针对words1和words2，相同index的字符串的对应关系，可能是a:b、b:a 也可能没有..
3. 当words1[i] == word2s[i]时，也符合相似题意 判断words1和words2是否相似...

思路：

1. 先判断words1和words2长度是否相等,若不同返回False
2. 之后将pairs转化为hashset，可以加快匹配查找的速度
3. 判断每次循环中是否为a == b (a,b) (b,a)这三种状态，若不是返回False
4. 最终匹配无异常，返回True

解题：

class Solution:
    def areSentencesSimilar(self, sentence1, sentence2, similarPairs):
        if len(sentence1) != len(sentence2):
            return False
        sim = set(map(tuple, similarPairs))
        for i in range(len(sentence1)):
            s1, s2 = sentence1[i], sentence2[i]
            if s1 == s2 or (s1, s2) in sim or (s2, s1) in sim:
                continue
            return False
        return True

欢迎关注我的公众号: 清风Python，带你每日学习Python算法刷题的同时，了解更多python小知识。

有喜欢力扣刷题的小伙伴可以加我微信（King_Uranus）互相鼓励，共同进步，一起玩转超级码力！

我的个人博客：https://qingfengpython.cn

力扣解题合集：https://github.com/BreezePython/AlgorithmMarkdown