734. Sentence Similarity 句子相似性

题目地址：https://leetcode-cn.com/problems/sentence-similarity/

题目描述

Given two sentences words1, words2 (each represented as an array of strings), and a list of similar word pairs pairs, determine if two sentences are similar.

Forexample, "great acting skills" and "fine drama talent" are similar, if the similar word pairs are pairs = [["great", "fine"], ["acting","drama"], ["skills","talent"]].

Note that the similarity relation is not transitive. For example, if "great" and "fine" are similar, and "fine" and "good" are similar, "great" and "good" are not necessarily similar.

However, similarity is symmetric. For example, "great" and "fine" being similar is the same as "fine" and "great" being similar.

Also, a word is always similar with itself. For example, the sentences words1 = ["great"], words2 = ["great"], pairs = [] are similar, even though there are no specified similar word pairs.

Finally, sentences can only be similar if they have the same number of words. So a sentence like words1 = ["great"] can never be similar to words2 = ["doubleplus","good"].

Note:

1、 Thelengthofwords1andwords2willnotexceed1000.；
2、 Thelengthofpairswillnotexceed2000.；
3、 Thelengthofeachpairs[i]willbe2.；
4、 Thelengthofeachwords[i]andpairs[i][j]willbeintherange[1,20].；

题目大意

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

解题方法

只修改区间起终点

这个题有一个坑的地方没说清楚：一个词可能会和多个词相似。

因此使用map<string, set<string>>的方式，保存{每个词 : 与之相似的词}所有映射关系。

注意相似是双向的，因此对于一个Pair，需要正反插入两次。

判断是否相似的时候，需要对两个列表的对应元素进行遍历，判断是否相等或者在其相似set中出现。

C++代码如下：

class Solution {
public:
    bool areSentencesSimilar(vector<string>& words1, vector<string>& words2, vector<vector<string>>& pairs) {
        if (words1.size() != words2.size()) return false;
        const int N = words1.size();
        unordered_map<string, unordered_set<string>> similar;
        for (auto& pair : pairs) {
            similar[pair[0]].insert(pair[1]);
            similar[pair[1]].insert(pair[0]);
        }
        for (int i = 0; i < N; ++i) {
            if (words1[i] != words2[i] && !similar[words1[i]].count(words2[i])) {
                return false;
            }
        }
        return true;
    }
};

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

2022

DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有

本文经作者：负雪明烛授权发布，任何组织或个人未经作者授权不得转发