LWC 60:734. Sentence Similarity

LWC 60:734. Sentence Similarity

传送门:734. Sentence Similarity

Problem:

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. For example, “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:

The length of words1 and words2 will not exceed 1000.

The length of pairs will not exceed 2000.

The length of each pairs[i] will be 2.

The length of each words[i] and pairs[i][j] will be in the range [1, 20].

思路: 查询每个单词是否有对应的近义词,如果找不到则返回false。

Java版:

    public boolean areSentencesSimilar(String[] words1, String[] words2, String[][] pairs) {
        if (words1.length != words2.length) return false;
        Map<String, Set<String>> map = new HashMap<>();
        for (String[] p : pairs) {
            map.computeIfAbsent(p[0], k -> new HashSet<>()).add(p[1]);
        }

        for (int i = 0; i < words1.length; ++i) {
            String a = words1[i];
            String b = words2[i];
            if (!a.equals(b)) {
                if (!map.getOrDefault(a, new HashSet<>()).contains(b) && !map.getOrDefault(b, new HashSet<>()).contains(a)) return false;
            }
        }
        return true;
    }

Python版:

    def areSentencesSimilar(self, words1, words2, pairs):
        """
        :type words1: List[str]
        :type words2: List[str]
        :type pairs: List[List[str]]
        :rtype: bool
        """
        from collections import  defaultdict
        n1 = len(words1)
        n2 = len(words2)

        if n1 != n2:
            return False

        map = defaultdict(set)
        for word1, word2 in pairs:
            map[word1].add(word2)
        for word1, word2 in zip(words1, words2):
            if word1 != word2 and word2 not in map[word1] and word1 not in map[word2]:
                return False
        return True

Python 注意 all 的使用:

all([…]) or all((…)) 所有元素不为空,不为0,不为Flase,则返回True

    def areSentencesSimilar(self, words1, words2, pairs):
        """
        :type words1: List[str]
        :type words2: List[str]
        :type pairs: List[List[str]]
        :rtype: bool
        """
        from collections import  defaultdict
        n1 = len(words1)
        n2 = len(words2)

        if n1 != n2:
            return False

        map = defaultdict(set)
        for w in words1:
            map[w].add(w)

        for w in words2:
            map[w].add(w)

        for word1, word2 in pairs:
            map[word1].add(word2)
            map[word2].add(word1)
        return all(b in map[a] for a, b in zip(words1, words2))     

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏大内老A

深入理解C# 3.x的新特性(2):Extension Method[下篇]

四、Extension Method的本质 通过上面一节的介绍,我们知道了在C#中如何去定义一个Extension Method:它是定义在一个Static c...

1969
来自专栏大内老A

从yield关键字看IEnumerable和Collection的区别

C#的yield关键字由来以久,如果我没有记错的话,应该是在C# 2.0中被引入的。相信大家此关键字的用法已经了然于胸,很多人也了解yield背后的“延迟赋值”...

2137
来自专栏GreenLeaves

C# 委托基础

不知不觉,又开始委托的学习了,感觉这个东西我能学一辈子,哈哈哈!这次看的是官方的参考书(C#高编9),每次看不同的资料,总能学到不同的知识!言归正传 1、为什么...

1905
来自专栏大内老A

《深入理解C# 3.x的新特性》博文系列汇总

较之C# 2.0, C# 3.x引入了一系列新的特性,为我们编程带来很大的便利,通过有效地利用这些新特性,我们可以编写出更加简洁、优雅的程序。不过这些新特性仅仅...

1948
来自专栏IT进修之路

原 分分钟看懂java用引用传递与值传递在

1805
来自专栏偏前端工程师的驿站

JS魔法堂:再识Bitwise Operation & Bitwise Shift

Brief                                 linkFly的《JavaScript-如果...没有方法》中提及如何手写Math....

2089
来自专栏hbbliyong

LINQ查询操作符 LINQ学习第二篇

一、投影操作符 1. Select Select操作符对单个序列或集合中的值进行投影。下面的示例中使用select从序列中返回Employee表的所有列: ...

3605
来自专栏菩提树下的杨过

数据结构C#版笔记--单链表(LinkList)

上一篇学习了"顺序表(SeqList)",这一篇来看下“单链表(LinkList)”。在上一篇的最后,我们指出了:顺序表要求开辟一组连续的内存空间,而且插入/删...

2187
来自专栏james大数据架构

c#字符串操作方法实例

# 字符串是使用 string 关键字声明的一个字符数组。字符串是使用引号声明的,如下例所示: string s = "Hello, World!"; 字符串...

2278
来自专栏风口上的猪的文章

.NET面试题系列[9] - IEnumerable

IEnumerable及IEnumerable的泛型版本IEnumerable<T>是一个接口,它只含有一个方法GetEnumerator。Enumerable...

1062

扫码关注云+社区